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: | Article in Journal/Newspaper |
Language: | unknown |
Published: |
arXiv
2022
|
Subjects: | |
Online Access: | https://dx.doi.org/10.48550/arxiv.2201.00328 https://arxiv.org/abs/2201.00328 |
id |
ftdatacite:10.48550/arxiv.2201.00328 |
---|---|
record_format |
openpolar |
spelling |
ftdatacite:10.48550/arxiv.2201.00328 2023-05-15T16:31:27+02:00 Implicit representation of sparse hereditary families Alon, Noga 2022 https://dx.doi.org/10.48550/arxiv.2201.00328 https://arxiv.org/abs/2201.00328 unknown arXiv Creative Commons Attribution 4.0 International https://creativecommons.org/licenses/by/4.0/legalcode cc-by-4.0 CC-BY Combinatorics math.CO Discrete Mathematics cs.DM FOS Mathematics FOS Computer and information sciences G.2.2 05C78, 68R10 article Preprint Article CreativeWork 2022 ftdatacite https://doi.org/10.48550/arxiv.2201.00328 2022-02-09T11:17:09Z 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. Article in Journal/Newspaper Groenland DataCite Metadata Store (German National Library of Science and Technology) |
institution |
Open Polar |
collection |
DataCite Metadata Store (German National Library of Science and Technology) |
op_collection_id |
ftdatacite |
language |
unknown |
topic |
Combinatorics math.CO Discrete Mathematics cs.DM FOS Mathematics FOS Computer and information sciences G.2.2 05C78, 68R10 |
spellingShingle |
Combinatorics math.CO Discrete Mathematics cs.DM FOS Mathematics FOS Computer and information sciences G.2.2 05C78, 68R10 Alon, Noga Implicit representation of sparse hereditary families |
topic_facet |
Combinatorics math.CO Discrete Mathematics cs.DM FOS Mathematics FOS Computer and information sciences G.2.2 05C78, 68R10 |
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 |
Article in Journal/Newspaper |
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 |
publisher |
arXiv |
publishDate |
2022 |
url |
https://dx.doi.org/10.48550/arxiv.2201.00328 https://arxiv.org/abs/2201.00328 |
genre |
Groenland |
genre_facet |
Groenland |
op_rights |
Creative Commons Attribution 4.0 International https://creativecommons.org/licenses/by/4.0/legalcode cc-by-4.0 |
op_rightsnorm |
CC-BY |
op_doi |
https://doi.org/10.48550/arxiv.2201.00328 |
_version_ |
1766021163283120128 |