The Lovász conjecture holds for moderately dense Cayley graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911607549853696 |
|---|---|
| author | Bedert, Benjamin Draganić, Nemanja Müyesser, Alp Pavez-Signé, Matías |
| author_facet | Bedert, Benjamin Draganić, Nemanja Müyesser, Alp Pavez-Signé, Matías |
| contents | We show that there is an absolute constant $c>0$ such that every large connected $n$-vertex Cayley graph with degree $d\geq n^{1-c}$ has a Hamilton cycle. This makes progress towards the Lovász conjecture and improves upon the previous best result of this form due to Christofides, Hladký, and Máthé from 2014 concerning graphs with $d\geq \varepsilon n$. Our proof avoids the use of Szemerédi's regularity lemma and relies instead on an efficient arithmetic regularity lemma specialised to Cayley graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_08675 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | The Lovász conjecture holds for moderately dense Cayley graphs Bedert, Benjamin Draganić, Nemanja Müyesser, Alp Pavez-Signé, Matías Combinatorics Group Theory 05C38, 05C35 We show that there is an absolute constant $c>0$ such that every large connected $n$-vertex Cayley graph with degree $d\geq n^{1-c}$ has a Hamilton cycle. This makes progress towards the Lovász conjecture and improves upon the previous best result of this form due to Christofides, Hladký, and Máthé from 2014 concerning graphs with $d\geq \varepsilon n$. Our proof avoids the use of Szemerédi's regularity lemma and relies instead on an efficient arithmetic regularity lemma specialised to Cayley graphs. |
| title | The Lovász conjecture holds for moderately dense Cayley graphs |
| topic | Combinatorics Group Theory 05C38, 05C35 |
| url | https://arxiv.org/abs/2603.08675 |