An efficient implicit representation of an $n$-vertex graph $G$ in a family $\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 $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^{\Omega(1)}$.
翻译:在家庭 $\ mathcal{F} 图表中,一个有效的隐含代表 $n- verdex 图形 $G$ 在家庭 $\ mathcal{F}$G$ 中, 向每个顶点指定了一个长度为$G$的二进制代码 $O (\log n), 这样每对脊椎之间的相邻性只能根据其代码的函数来确定。 这个函数可以取决于家庭, 而不是取决于个人图表。 每一个承认这种代表的图表家庭, 最多包含$n o(n\log(n)) $ 的图表, 并因此以大多数因数增长速度为因数。 隐含的假设表明, 反过来说, 每个具有最大因数增长速度的遗传图家族, 都承认一种有效的隐含代表。 我们反驳这一推论, 其方法是确定遗传图家庭的存在具有因数增长速度, 需要长度 $\\\\\\ (1)美元的代码 $。