2022/01/02 by Alon, Noga
#05C78 #68R10 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #G.2.2
paper · doi:10.48550/arxiv.2201.00328
For a hereditary family of graphs \FF, let \FFn denote the set of all members of \FF on n vertices. The speed of \FF is the function f(n)=|\FFn|. An implicit representation of size ℓ(n) for \FFn is a function assigning a label of ℓ(n) bits to each vertex of any given graph G ∈ \FFn, 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 \FFn for any hereditary family \FF with speed 2Ω(n2) is (1+o(1)) log2 |\FFn|/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 2O(n log n) that do not admit implicit representations of size smaller than n1/2-δ. In this note we show that even a mild speed bound ensures an implicit representation of size O(nc) 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)n2 then \FFn admits an implicit representation of size O(n1-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.