## 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^{Ω}^{(}n^{2}) 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(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-ε)}n^{2} then F_{n} admits an implicit representation of size O(n^{1-1/d}logn). 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) |
---|---|

Pages (from-to) | 476-482 |

Number of pages | 7 |

Journal | Discrete and Computational Geometry |

Volume | 72 |

Issue number | 2 |

DOIs | |

State | Published - Sep 2024 |

## All Science Journal Classification (ASJC) codes

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

## Keywords

- (Induced)-universal graphs
- 05C62
- 05C78
- 52C10
- Hereditary properties
- Implicit representation
- Shatter function
- VC-dimension