Bonnet, Edouard, Duron, Julien, Sylvester, John 
ORCID: 0000-0002-6543-2934, Zamaraev, Viktor ORCID: 0000-0001-5755-4141 and Zhukovskii, Maksim
(2024)
Small But Unwieldy: A Lower Bound on Adjacency Labels for Small Classes.
In: ACM-SIAM Symposium on Discrete Algorithms (SODA24).
|
Text
SmallIsBig2.pdf - Author Accepted Manuscript Download (679kB) | Preview |
Abstract
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 ns. 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 2O(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 2o(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.
| Item Type: | Conference or Workshop Item (Unspecified) |
|---|---|
| Divisions: | Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 11 Dec 2023 11:47 |
| Last Modified: | 10 Apr 2024 10:15 |
| DOI: | 10.1137/1.9781611977912.44 |
| Related URLs: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3177254 |
Dimensions
Dimensions
