## Abstract

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 _{2}| 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}^{(}^{n}^{log}^{n}^{)} 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}^{/}^{d}log n) . Moreover, for every integer d> 1 there is a hereditary family for which this is tight up to the logarithmic factor.

Original language | English (US) |
---|---|

Journal | Discrete and Computational Geometry |

DOIs | |

State | Accepted/In press - 2023 |

## All Science Journal Classification (ASJC) codes

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

## Keywords

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