Implicit representation of sparse hereditary families
For a hereditary family of graphs $\FF$, let $\FF_n$ denote the set of all members of $\FF$ on $n$ vertices. The speed of $\FF$ is the function $f(n)=|\FF_n|$. An implicit representation of size $\ell(n)$ for $\FF_n$ is a function assigning a label of $\ell(n)$ bits to each vertex of any given graph...
Main Author: | |
---|---|
Format: | Text |
Language: | unknown |
Published: |
2022
|
Subjects: | |
Online Access: | http://arxiv.org/abs/2201.00328 |
id |
ftarxivpreprints:oai:arXiv.org:2201.00328 |
---|---|
record_format |
openpolar |
spelling |
ftarxivpreprints:oai:arXiv.org:2201.00328 2023-09-05T13:19:58+02:00 Implicit representation of sparse hereditary families Alon, Noga 2022-01-02 http://arxiv.org/abs/2201.00328 unknown http://arxiv.org/abs/2201.00328 Mathematics - Combinatorics Computer Science - Discrete Mathematics 05C78 68R10 G.2.2 text 2022 ftarxivpreprints 2023-08-16T16:51:55Z For a hereditary family of graphs $\FF$, let $\FF_n$ denote the set of all members of $\FF$ on $n$ vertices. The speed of $\FF$ is the function $f(n)=|\FF_n|$. An implicit representation of size $\ell(n)$ for $\FF_n$ is a function assigning a label of $\ell(n)$ bits to each vertex of any given graph $G \in \FF_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 $\FF_n$ for any hereditary family $\FF$ with speed $2^{\Omega(n^2)}$ is $(1+o(1)) \log_2 |\FF_n|/n~(=\Theta(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 $\delta>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-\delta}$. 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 $\eps>0$ there is an integer $d \geq 1$ so that if $\FF$ is a hereditary family with speed $f(n) \leq 2^{(1/4-\eps)n^2}$ then $\FF_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. Text Groenland ArXiv.org (Cornell University Library) |
institution |
Open Polar |
collection |
ArXiv.org (Cornell University Library) |
op_collection_id |
ftarxivpreprints |
language |
unknown |
topic |
Mathematics - Combinatorics Computer Science - Discrete Mathematics 05C78 68R10 G.2.2 |
spellingShingle |
Mathematics - Combinatorics Computer Science - Discrete Mathematics 05C78 68R10 G.2.2 Alon, Noga Implicit representation of sparse hereditary families |
topic_facet |
Mathematics - Combinatorics Computer Science - Discrete Mathematics 05C78 68R10 G.2.2 |
description |
For a hereditary family of graphs $\FF$, let $\FF_n$ denote the set of all members of $\FF$ on $n$ vertices. The speed of $\FF$ is the function $f(n)=|\FF_n|$. An implicit representation of size $\ell(n)$ for $\FF_n$ is a function assigning a label of $\ell(n)$ bits to each vertex of any given graph $G \in \FF_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 $\FF_n$ for any hereditary family $\FF$ with speed $2^{\Omega(n^2)}$ is $(1+o(1)) \log_2 |\FF_n|/n~(=\Theta(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 $\delta>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-\delta}$. 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 $\eps>0$ there is an integer $d \geq 1$ so that if $\FF$ is a hereditary family with speed $f(n) \leq 2^{(1/4-\eps)n^2}$ then $\FF_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. |
format |
Text |
author |
Alon, Noga |
author_facet |
Alon, Noga |
author_sort |
Alon, Noga |
title |
Implicit representation of sparse hereditary families |
title_short |
Implicit representation of sparse hereditary families |
title_full |
Implicit representation of sparse hereditary families |
title_fullStr |
Implicit representation of sparse hereditary families |
title_full_unstemmed |
Implicit representation of sparse hereditary families |
title_sort |
implicit representation of sparse hereditary families |
publishDate |
2022 |
url |
http://arxiv.org/abs/2201.00328 |
genre |
Groenland |
genre_facet |
Groenland |
op_relation |
http://arxiv.org/abs/2201.00328 |
_version_ |
1776200732139061248 |