Implicit Representation of Sparse Hereditary Families

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
JournalDiscrete and Computational Geometry
StateAccepted/In press - 2023

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics


  • (Induced)-universal graphs
  • Hereditary properties
  • Implicit representation
  • Shatter function
  • VC-dimension


Dive into the research topics of 'Implicit Representation of Sparse Hereditary Families'. Together they form a unique fingerprint.

Cite this