Improved bound on the number of cycle sets
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912597732753408 |
|---|---|
| author | Nenadov, Rajko |
| author_facet | Nenadov, Rajko |
| contents | The cycle set of a graph $G$ is the set consisting of all sizes of cycles in $G$. Answering a conjecture of Erdős and Faudree, Verstraëte showed that there are at most $2^{n - n^{1/10}}$ different cycle sets of graphs with $n$ vertices. We improve this bound to $2^{n - n^{1/2 - o(1)}}$. Our proof follows the general strategy of Verstraëte of reducing the problem to counting cycle sets of Hamiltonian graphs with many chords or a large maximum degree. The key new ingredients are near-optimal container lemmata for cycle sets of such graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_09904 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Improved bound on the number of cycle sets Nenadov, Rajko Combinatorics The cycle set of a graph $G$ is the set consisting of all sizes of cycles in $G$. Answering a conjecture of Erdős and Faudree, Verstraëte showed that there are at most $2^{n - n^{1/10}}$ different cycle sets of graphs with $n$ vertices. We improve this bound to $2^{n - n^{1/2 - o(1)}}$. Our proof follows the general strategy of Verstraëte of reducing the problem to counting cycle sets of Hamiltonian graphs with many chords or a large maximum degree. The key new ingredients are near-optimal container lemmata for cycle sets of such graphs. |
| title | Improved bound on the number of cycle sets |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2501.09904 |