Implicit Representation of Sparse Hereditary Families

For a hereditary family of graphs F, let F_n denote the set of all members of F on n vertices. The speed of F is the function f(n)=|F_n|. An implicit representation of size ℓ(n) for F_n is a function assigning a label of ℓ(n) bits to each vertex of any given graph G∈F_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 F_n for any hereditary family F with speed 2^Ω(n²) is (1+o(1))log₂|F_n|/n (=Θ(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 δ>0 there are hereditary families of graphs with speed 2^O(nlogn) that do not admit implicit representations of size smaller than n^1/2-δ. 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 ε>0 there is an integer d≥1 so that if F is a hereditary family with speed f(n)≤2^(1/4-ε)n² then F_n admits an implicit representation of size O(n^1-1/dlogn). Moreover, for every integer d>1 there is a hereditary family for which this is tight up to the logarithmic factor.