Tight bounds on adjacency labels for monotone graph classes
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916131707551744 |
|---|---|
| author | Bonnet, Édouard Duron, Julien Sylvester, John Zamaraev, Viktor Zhukovskii, Maksim |
| author_facet | Bonnet, Édouard Duron, Julien Sylvester, John Zamaraev, Viktor Zhukovskii, Maksim |
| contents | A class of graphs admits an adjacency labeling scheme of size $b(n)$, if the vertices in each of its $n$-vertex graphs can be assigned binary strings (called labels) of length $b(n)$ so that the adjacency of two vertices can be determined solely from their labels.
We give tight bounds on the size of adjacency labels for every family of monotone (i.e., subgraph-closed) classes with a well-behaved growth function between $2^{O(n \log n)}$ and $2^{O(n^{2-δ})}$ for any $δ> 0$. Specifically, we show that for any function $f: \mathbb N \to \mathbb R$ satisfying $\log n \leqslant f(n) \leqslant n^{1-δ}$ for any fixed $δ> 0$, and some~sub-multiplicativity condition, there are monotone graph classes with growth $2^{O(nf(n))}$ that do not admit adjacency labels of size at most $f(n) \log n$. On the other hand, any such class does admit adjacency labels of size $O(f(n)\log n)$. Surprisingly this tight bound is a $Θ(\log n)$ factor away from the information-theoretic bound of $Ω(f(n))$. The special case when $f = \log$ implies that the recently-refuted Implicit Graph Conjecture [Hatami and Hatami, FOCS 2022] also fails within monotone classes.
We further show that the Implicit Graph Conjecture holds for all monotone \emph{small} classes. In other words, any monotone class with growth rate at most $n!\,c^n$ for some constant $c>0$, admits adjacency labels of information-theoretic order optimal size. In fact, we show a more general result that is of independent interest: any monotone small class of graphs has bounded degeneracy.We conjecture that the Implicit Graph Conjecture holds for all hereditary small classes. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_20522 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Tight bounds on adjacency labels for monotone graph classes Bonnet, Édouard Duron, Julien Sylvester, John Zamaraev, Viktor Zhukovskii, Maksim Combinatorics Discrete Mathematics Data Structures and Algorithms 68R01, 68R05, 05C80 G.2.1 A class of graphs admits an adjacency labeling scheme of size $b(n)$, if the vertices in each of its $n$-vertex graphs can be assigned binary strings (called labels) of length $b(n)$ so that the adjacency of two vertices can be determined solely from their labels. We give tight bounds on the size of adjacency labels for every family of monotone (i.e., subgraph-closed) classes with a well-behaved growth function between $2^{O(n \log n)}$ and $2^{O(n^{2-δ})}$ for any $δ> 0$. Specifically, we show that for any function $f: \mathbb N \to \mathbb R$ satisfying $\log n \leqslant f(n) \leqslant n^{1-δ}$ for any fixed $δ> 0$, and some~sub-multiplicativity condition, there are monotone graph classes with growth $2^{O(nf(n))}$ that do not admit adjacency labels of size at most $f(n) \log n$. On the other hand, any such class does admit adjacency labels of size $O(f(n)\log n)$. Surprisingly this tight bound is a $Θ(\log n)$ factor away from the information-theoretic bound of $Ω(f(n))$. The special case when $f = \log$ implies that the recently-refuted Implicit Graph Conjecture [Hatami and Hatami, FOCS 2022] also fails within monotone classes. We further show that the Implicit Graph Conjecture holds for all monotone \emph{small} classes. In other words, any monotone class with growth rate at most $n!\,c^n$ for some constant $c>0$, admits adjacency labels of information-theoretic order optimal size. In fact, we show a more general result that is of independent interest: any monotone small class of graphs has bounded degeneracy.We conjecture that the Implicit Graph Conjecture holds for all hereditary small classes. |
| title | Tight bounds on adjacency labels for monotone graph classes |
| topic | Combinatorics Discrete Mathematics Data Structures and Algorithms 68R01, 68R05, 05C80 G.2.1 |
| url | https://arxiv.org/abs/2310.20522 |