Hamiltonicity of regular sublinear expanders
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866911685884772352 |
|---|---|
| author | Bradač, Domagoj Janzer, Oliver |
| author_facet | Bradač, Domagoj Janzer, Oliver |
| contents | We say that a $d$-regular graph is a $γ$-expander if for every not too large set of vertices $S$, there are at least $γd |S|$ edges leaving $S$, and we say that a graph $G$ is $γ$-far from bipartite if at least $γe(G)$ edges need to be removed to make it bipartite. We prove that there exists an absolute constant $K$ such that any $n$-vertex $d$-regular $γ$-expander with $d \ge (γ^{-1} \log n)^K$ is Hamiltonian, provided that it is bipartite or $γ$-far from bipartite. As applications, we obtain highly robust versions of recent important results on the Hamiltonicity of Cayley graphs and Kneser graphs. As part of our proof, we prove a random connecting lemma for sublinear expanders which might be of independent interest. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_15043 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Hamiltonicity of regular sublinear expanders Bradač, Domagoj Janzer, Oliver Combinatorics We say that a $d$-regular graph is a $γ$-expander if for every not too large set of vertices $S$, there are at least $γd |S|$ edges leaving $S$, and we say that a graph $G$ is $γ$-far from bipartite if at least $γe(G)$ edges need to be removed to make it bipartite. We prove that there exists an absolute constant $K$ such that any $n$-vertex $d$-regular $γ$-expander with $d \ge (γ^{-1} \log n)^K$ is Hamiltonian, provided that it is bipartite or $γ$-far from bipartite. As applications, we obtain highly robust versions of recent important results on the Hamiltonicity of Cayley graphs and Kneser graphs. As part of our proof, we prove a random connecting lemma for sublinear expanders which might be of independent interest. |
| title | Hamiltonicity of regular sublinear expanders |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2605.15043 |