SODA Conference 2024 Conference Paper
- Édouard Bonnet
- Julien Duron
- John Sylvester 0001
- Viktor Zamaraev
- Maksim Zhukovskii
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 min{ p, 1— p } < δ/n with δ < 1, then with high probability even the number of all unlabeled (not necessarily induced) subgraphs is 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.