Implicit Graph Conjecture

Definitions and mathematical statement

Shared notation.

$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

Let $\mathcal G$ be a family of finite simple graphs closed under graph isomorphism. It is hereditary if every induced subgraph of a member is also a member. Let $\mathcal G_n$ be its graphs with labeled vertex set $\{1,\ldots,n\}$. It has at most factorial speed when some constant $C$ satisfies \[ |\mathcal G_n|\le 2^{C n\log_2(n+1)}\quad(n\ge1). \] An implicit adjacency representation assigns to each vertex of each $G\in\mathcal G_n$ a binary label of length at most $c\lceil\log_2(n+1)\rceil$, for one constant $c$, together with a fixed decoder $D$ on pairs of binary strings such that for distinct $u,v$, \[ uv\in E(G)\quad\Longleftrightarrow\quad D(\ell_G(u),\ell_G(v))=1. \] The decoder may depend on the family but not on the individual graph. The original algorithmic convention also requires $D$ to be computable in polynomial time in the label lengths; the source's negative result permits even unrestricted decoders.

Statement recorded in the supplied source.

Does every hereditary family of at most factorial speed admit an implicit adjacency representation with labels of length $O(\log n)$, in the above original algorithmic convention? The factorial growth condition is the precise standard meaning of the catalogue's “slowly-growing” family, as identified in its literature review. The same existence question with unrestricted decoders is also refuted by Source S2. [S2]

Short English statement

Must every hereditary graph family with at most factorially many labeled graphs have logarithmic-size vertex labels from which adjacency can be decoded?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 1439 (GRAPH-052). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Hamed Hatami and Pooya Hatami, The Implicit Graph Conjecture Is False, arXiv:2111.13198v2 (2021), Section 1, Conjecture 1.3 and Theorem 1.4, pages 1--3. https://arxiv.org/pdf/2111.13198v2.