%0 Generic %1 alon2022implicit %A Alon, Noga %D 2022 %K compression graph thesis_topic %T Implicit representation of sparse hereditary families %U http://arxiv.org/abs/2201.00328 %X For a hereditary family of graphs $\FF$, let $\FF_n$ denote the set of all members of $\FF$ on $n$ vertices. The speed of $\FF$ is the function $f(n)=|\FF_n|$. An implicit representation of size $\ell(n)$ for $\FF_n$ is a function assigning a label of $\ell(n)$ bits to each vertex of any given graph $G \FF_n$, so that the adjacency between any pair of vertices can be determined by their labels. Bonamy, Esperet, Groenland and Scott proved that the minimum possible size of an implicit representation of $\FF_n$ for any hereditary family $\FF$ with speed $2^Ømega(n^2)$ is $(1+o(1)) łog_2 |\FF_n|/n~(=\Theta(n))$. A recent result of Hatami and Hatami shows that the situation is very different for very sparse hereditary families. They showed that for every $\delta>0$ there are hereditary families of graphs with speed $2^O(n n)$ that do not admit implicit representations of size smaller than $n^1/2-\delta$. In this note we show that even a mild speed bound ensures an implicit representation of size $O(n^c)$ for some $c<1$. Specifically we prove that for every $\eps>0$ there is an integer $d 1$ so that if $\FF$ is a hereditary family with speed $f(n) 2^(1/4-\eps)n^2$ then $\FF_n$ admits an implicit representation of size $O(n^1-1/d n)$. Moreover, for every integer $d>1$ there is a hereditary family for which this is tight up to the logarithmic factor.

@misc{alon2022implicit, abstract = {For a hereditary family of graphs $\FF$, let $\FF_n$ denote the set of all members of $\FF$ on $n$ vertices. The speed of $\FF$ is the function $f(n)=|\FF_n|$. An implicit representation of size $\ell(n)$ for $\FF_n$ is a function assigning a label of $\ell(n)$ bits to each vertex of any given graph $G \in \FF_n$, so that the adjacency between any pair of vertices can be determined by their labels. Bonamy, Esperet, Groenland and Scott proved that the minimum possible size of an implicit representation of $\FF_n$ for any hereditary family $\FF$ with speed $2^{\Omega(n^2)}$ is $(1+o(1)) \log_2 |\FF_n|/n~(=\Theta(n))$. A recent result of Hatami and Hatami shows that the situation is very different for very sparse hereditary families. They showed that for every $\delta>0$ there are hereditary families of graphs with speed $2^{O(n \log n)}$ that do not admit implicit representations of size smaller than $n^{1/2-\delta}$. In this note we show that even a mild speed bound ensures an implicit representation of size $O(n^c)$ for some $c<1$. Specifically we prove that for every $\eps>0$ there is an integer $d \geq 1$ so that if $\FF$ is a hereditary family with speed $f(n) \leq 2^{(1/4-\eps)n^2}$ then $\FF_n$ admits an implicit representation of size $O(n^{1-1/d} \log n)$. Moreover, for every integer $d>1$ there is a hereditary family for which this is tight up to the logarithmic factor.}, added-at = {2022-01-04T14:05:33.000+0100}, author = {Alon, Noga}, biburl = {https://www.bibsonomy.org/bibtex/2973073cee8245633e0c5231046849bc8/j.c.m.janssen}, description = {Implicit representation of sparse hereditary families}, interhash = {31aad69eb3e67eecda359c9894a12cf4}, intrahash = {973073cee8245633e0c5231046849bc8}, keywords = {compression graph thesis_topic}, note = {cite arxiv:2201.00328}, timestamp = {2022-01-04T14:05:33.000+0100}, title = {Implicit representation of sparse hereditary families}, url = {http://arxiv.org/abs/2201.00328}, year = 2022 }