Lune

FOCS2022Top-tier venue

The Implicit Graph Conjecture is False

Hamed Hatami, Pooya Hatami

Abstract

An efficient implicit representation of an n-vertex graph G in a family F\mathcal{F} of graphs assigns to each vertex of G a binary code of length O(log n) so that the adjacency between every pair of vertices can be determined only as a function of their codes. This function can depend on the family but not on the individual graph. Every family of graphs admitting such a representation contains at most 2O(nlog⁡(n))2^{O(n\log(n))} graphs on n vertices, and thus has at most factorial speed of growth. The Implicit Graph Conjecture states that, conversely, every hereditary graph family with at most factorial speed of growth admits an efficient implicit representation. We refute this conjecture by establishing the existence of hereditary graph families with factorial speed of growth that require codes of length nΩ(1)n^{\Omega(1)}.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

6 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • No Complete Problem for Constant-Cost Randomized Communication cites Adjacency Sketches in Adversarial Environments
  • No Complete Problem for Constant-Cost Randomized Communication cites Randomized Communication and Implicit Representations for Matrices and Graphs of Small Sign-Rank
  • No Complete Problem for Constant-Cost Randomized Communication cites Randomized communication and implicit graph representations
  • Randomized communication and implicit graph representations cites No Complete Problem for Constant-Cost Randomized Communication
  • The Meta-complexity of Secret Sharing cites No Complete Problem for Constant-Cost Randomized Communication
  • The Meta-complexity of Secret Sharing cites Randomized communication and implicit graph representations
  • Adjacency Sketches in Adversarial Environments cites Randomized communication and implicit graph representations
  • Randomized communication and implicit graph representations cites Adjacency Sketches in Adversarial Environments
  • Twin-width II: small classes cites Adjacency Labelling for Planar Graphs (and Beyond)
  • Randomized Communication and Implicit Representations for Matrices and Graphs of Small Sign-Rank cites Randomized communication and implicit graph representations
  • Optimal labelling schemes for adjacency, comparability, and reachability cites Twin-width II: small classes
  • Optimal labelling schemes for adjacency, comparability, and reachability cites Adjacency Labelling for Planar Graphs (and Beyond)
  • Randomized communication and implicit graph representations cites Twin-width II: small classes
  • Randomized communication and implicit graph representations cites Adjacency Labelling for Planar Graphs (and Beyond)
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers6

  1. Randomized communication and implicit graph representationsNathaniel Harms, Sebastian Wild, Viktor ZamaraevSTOC 2022 · 11 citations
  2. No Complete Problem for Constant-Cost Randomized CommunicationYuting Fang, Lianna Hambardzumyan, Nathaniel Harms, Pooya HatamiSTOC 2024 · 4 citations
  3. Randomized Communication and Implicit Representations for Matrices and Graphs of Small Sign-RankNathaniel Harms, Viktor ZamaraevSODA 2024 · 4 citations
  4. The Meta-complexity of Secret SharingBenny Applebaum, Oded NirSTOC 2025 · 2 citations
  5. Adjacency Sketches in Adversarial EnvironmentsMoni Naor, Eugene PekelSODA 2024 · 1 citation

Builds on3

  1. Twin-width II: small classesÉdouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Thomassé et al.SODA 2021 · 61 citations
  2. Adjacency Labelling for Planar Graphs (and Beyond)Vida Dujmovic, Louis Esperet, Cyril Gavoille, Gwenaël Joret et al.FOCS 2020 · 31 citations
  3. Optimal labelling schemes for adjacency, comparability, and reachabilityMarthe Bonamy, Louis Esperet, Carla Groenland, Alex D. ScottSTOC 2021

Related papers

  1. Small But Unwieldy: A Lower Bound on Adjacency Labels for Small ClassesEdouard Bonnet, Julien Duron, John Sylvester, Viktor Zamaraev et al.SODA 2024
  2. Shorter Labeling Schemes for Planar GraphsMarthe Bonamy, Cyril Gavoille, Michal PilipczukSODA 2020 · 24 citations
  3. New Oracles and Labeling Schemes for Vertex Cut QueriesYonggang Jiang, Merav Parter, Asaf PetruschkaSODA 2026
  4. Graph Homomorphism ConvolutionHoang Nguyen, Takanori MaeharaICML 2020 · 45 citations
  5. Twin-width IV: ordered graphs and matricesÉdouard Bonnet, Ugo Giocanti, Patrice Ossona de Mendez, Pierre Simon et al.STOC 2022 · 30 citations
Dusk over the sea between two cliffs drawn in fine vertical lines