2026-07-20T05:27:06Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20174 2024-07-02T07:52:49Z ddc:004 open_access

Tight Bounds on Adjacency Labels for Monotone Graph Classes Bonnet, Édouard Duron, Julien Sylvester, John Zamaraev, Viktor Zhukovskii, Maksim Adjacency labeling degeneracy monotone classes small classes factorial classes implicit graph conjecture 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 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^Ω(n log n) and 2^O(n^{2-δ}) for any δ > 0. Specifically, we show that for any function f: ℕ → ℝ satisfying log n ⩽ f(n) ⩽ 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 bound is a Θ(log n) factor away from the information-theoretic bound of Ω(f(n)). Our bounds are tight upto constant factors, and 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 small classes. In other words, any monotone class with growth rate at most n! cⁿ 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Édouard Bonnet and Julien Duron and John Sylvester and Viktor Zamaraev and Maksim Zhukovskii 2024 Is Part Of LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2024.31 urn:nbn:de:0030-drops-201741 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.31 eng https://creativecommons.org/licenses/by/4.0/legalcode