Hamilton cycles in pseudorandom graphs: resilience and approximate decompositions
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866918107821375488 |
|---|---|
| author | Draganić, Nemanja Kim, Jaehoon Lee, Hyunwoo Correia, David Munhá Pavez-Signé, Matías Sudakov, Benny |
| author_facet | Draganić, Nemanja Kim, Jaehoon Lee, Hyunwoo Correia, David Munhá Pavez-Signé, Matías Sudakov, Benny |
| contents | Dirac's classical theorem asserts that, for $n \ge 3$, any $n$-vertex graph with minimum degree at least $n/2$ is Hamiltonian. Furthermore, if we additionally assume that such graphs are regular, then, by the breakthrough work of Csaba, Kühn, Lo, Osthus and Treglown, they admit a decomposition into Hamilton cycles and at most one perfect matching, solving the well-known Nash-Williams conjecture. In the pseudorandom setting, it has long been conjectured that similar results hold in much sparser graphs. We prove two overarching theorems for graphs that exclude excessively dense subgraphs, which yield asymptotically optimal resilience and Hamilton-decomposition results in sparse pseudorandom graphs. In particular, our results imply that for every fixed $γ> 0$, there exists a constant $C > 0$ such that if $G$ is a spanning subgraph of an $(n,d,λ)$-graph satisfying $δ(G) \ge (\tfrac12 + γ)d$ and $d/λ\ge C$, then $G$ must contain a Hamilton cycle. Secondly, we show that for every $\varepsilon > 0$, there is $C > 0$ so that every $(n,d,λ)$-graph with $d/λ\ge C$ contains at least $(\tfrac12 - \varepsilon)d$ edge-disjoint Hamilton cycles, and, finally, we prove that the entire edge set of $G$ can be covered by no more than $(\tfrac12 + \varepsilon)d$ such cycles. All bounds are asymptotically optimal and significantly improve earlier results on Hamiltonian resilience, packing, and covering in sparse pseudorandom graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_22807 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Hamilton cycles in pseudorandom graphs: resilience and approximate decompositions Draganić, Nemanja Kim, Jaehoon Lee, Hyunwoo Correia, David Munhá Pavez-Signé, Matías Sudakov, Benny Combinatorics Dirac's classical theorem asserts that, for $n \ge 3$, any $n$-vertex graph with minimum degree at least $n/2$ is Hamiltonian. Furthermore, if we additionally assume that such graphs are regular, then, by the breakthrough work of Csaba, Kühn, Lo, Osthus and Treglown, they admit a decomposition into Hamilton cycles and at most one perfect matching, solving the well-known Nash-Williams conjecture. In the pseudorandom setting, it has long been conjectured that similar results hold in much sparser graphs. We prove two overarching theorems for graphs that exclude excessively dense subgraphs, which yield asymptotically optimal resilience and Hamilton-decomposition results in sparse pseudorandom graphs. In particular, our results imply that for every fixed $γ> 0$, there exists a constant $C > 0$ such that if $G$ is a spanning subgraph of an $(n,d,λ)$-graph satisfying $δ(G) \ge (\tfrac12 + γ)d$ and $d/λ\ge C$, then $G$ must contain a Hamilton cycle. Secondly, we show that for every $\varepsilon > 0$, there is $C > 0$ so that every $(n,d,λ)$-graph with $d/λ\ge C$ contains at least $(\tfrac12 - \varepsilon)d$ edge-disjoint Hamilton cycles, and, finally, we prove that the entire edge set of $G$ can be covered by no more than $(\tfrac12 + \varepsilon)d$ such cycles. All bounds are asymptotically optimal and significantly improve earlier results on Hamiltonian resilience, packing, and covering in sparse pseudorandom graphs. |
| title | Hamilton cycles in pseudorandom graphs: resilience and approximate decompositions |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2507.22807 |