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Ω(n2) 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-ε)n2 then F_n admits an implicit representation of size O(n^1-1/dlog n) . Moreover, for every integer d> 1 there is a hereditary family for which this is tight up to the logarithmic factor.