TY - JOUR
T1 - Implicit Representation of Sparse Hereditary Families
AU - Alon, Noga
N1 - Funding Information:
Research supported in part by NSF Grant DMS-2154082 and BSF Grant 2018267.
Publisher Copyright:
© 2023, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.
PY - 2023
Y1 - 2023
N2 - For a hereditary family of graphs F , let Fn denote the set of all members of F on n vertices. The speed of F is the function f(n) = | Fn| . An implicit representation of size ℓ(n) for Fn is a function assigning a label of ℓ(n) bits to each vertex of any given graph G∈ Fn , 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 Fn for any hereditary family F with speed 2Ω(n2) is (1 + o(1)) log 2| Fn| / 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 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 ε> 0 there is an integer d≥ 1 so that if F is a hereditary family with speed f(n)≤2(1/4-ε)n2 then Fn admits an implicit representation of size O(n1-1/dlog n) . Moreover, for every integer d> 1 there is a hereditary family for which this is tight up to the logarithmic factor.
AB - For a hereditary family of graphs F , let Fn denote the set of all members of F on n vertices. The speed of F is the function f(n) = | Fn| . An implicit representation of size ℓ(n) for Fn is a function assigning a label of ℓ(n) bits to each vertex of any given graph G∈ Fn , 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 Fn for any hereditary family F with speed 2Ω(n2) is (1 + o(1)) log 2| Fn| / 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 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 ε> 0 there is an integer d≥ 1 so that if F is a hereditary family with speed f(n)≤2(1/4-ε)n2 then Fn admits an implicit representation of size O(n1-1/dlog n) . Moreover, for every integer d> 1 there is a hereditary family for which this is tight up to the logarithmic factor.
KW - (Induced)-universal graphs
KW - Hereditary properties
KW - Implicit representation
KW - Shatter function
KW - VC-dimension
UR - http://www.scopus.com/inward/record.url?scp=85165482082&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85165482082&partnerID=8YFLogxK
U2 - 10.1007/s00454-023-00521-0
DO - 10.1007/s00454-023-00521-0
M3 - Article
AN - SCOPUS:85165482082
SN - 0179-5376
JO - Discrete and Computational Geometry
JF - Discrete and Computational Geometry
ER -