Small But Unwieldy: A Lower Bound on Adjacency Labels for Small Classes

We show that for any natural number s, there is a constant γ and a subgraph-closed class having, for any natural n, at most γ n graphs on n vertices up to isomorphism, but no adjacency labeling scheme with labels of size at most s log n. In other words, for every s, there is a small -even tiny-monotone class without universal graphs of size n s . Prior to this result, it was not excluded that every small class has an almost linear universal graph, or equivalently a labeling scheme with labels of size (1+o( 1)) log n. The existence of such a labeling scheme, a scaled-down version of the recently disproved Implicit Graph Conjecture, was repeatedly raised [Gavoille and Labourel, ESA '07; Dujmović et al., JACM '21; Bonamy et al., SIDMA '22; Bonnet et al., Comb. Theory '22]

. Furthermore, our small monotone classes have unbounded twin-width, thus simultaneously disprove the already-refuted Small conjecture; but this time with a self-contained proof, not relying on elaborate group-theoretic constructions.

As our main ingredient, we show that with high probability an Erdős-Rényi random graph G(n, p) with p = O(1/n) has, for every k ⩽ n, at most 2 O(k) subgraphs on k vertices, up to isomorphism. As a barrier to our general method of producing even more complex tiny classes, we show that when p = ω(1/n), the latter no longer holds. More concretely, we provide an explicit lower bound on the number of unlabeled k-vertex induced subgraphs of G(n, p) when 1/n ⩽ p ⩽ 1-1/n. We thereby obtain a threshold for the property of having exponentially many unlabeled induced subgraphs: if minp, 1 -p < δ/n with δ < 1, then with high probability even the number of all unlabeled (not necessarily induced) subgraphs is 2 o(n) , whereas if C/n < p < 1 -C/n for sufficiently large C, then with high probability the number of unlabeled induced subgraphs is 2 Θ(n) . This result supplements the study of counting unlabeled induced subgraphs that was initiated by Erdős and Rényi with a question on the number of unlabeled induced subgraphs of Ramsey graphs, eventually answered by Shelah.