Small But Unwieldy: A Lower Bound on Adjacency Labels for Small Classes
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917255528316928 |
|---|---|
| author | Bonnet, Édouard Duron, Julien Sylvester, John Zamaraev, Viktor Zhukovskii, Maksim |
| author_facet | Bonnet, Édouard Duron, Julien Sylvester, John Zamaraev, Viktor Zhukovskii, Maksim |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2307_11225 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Small But Unwieldy: A Lower Bound on Adjacency Labels for Small Classes Bonnet, Édouard Duron, Julien Sylvester, John Zamaraev, Viktor Zhukovskii, Maksim Combinatorics Discrete Mathematics Data Structures and Algorithms 68R01, 68R05, 05C80 G.2.1 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. |
| title | Small But Unwieldy: A Lower Bound on Adjacency Labels for Small Classes |
| topic | Combinatorics Discrete Mathematics Data Structures and Algorithms 68R01, 68R05, 05C80 G.2.1 |
| url | https://arxiv.org/abs/2307.11225 |