Hamiltonicity of Sparse Pseudorandom Graphs
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866916818602426368 |
|---|---|
| author | Ferber, Asaf Han, Jie Mao, Dingjia Vershynin, Roman |
| author_facet | Ferber, Asaf Han, Jie Mao, Dingjia Vershynin, Roman |
| contents | We show that every $(n,d,λ)$-graph contains a Hamilton cycle for sufficiently large $n$, assuming that $d\geq \log^{6}n$ and $λ\leq cd$, where $c=\frac{1}{70000}$. This significantly improves a recent result of Glock, Correia and Sudakov, who obtained a similar result for $d$ that grows polynomially with $n$. The proof is based on a new result regarding the second largest eigenvalue of the adjacency matrix of a subgraph induced by a random subset of vertices, combined with a recent result on connecting designated pairs of vertices by vertex-disjoint paths in $(n,d,λ)$-graphs. We believe that the former result is of independent interest and will have further applications. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_06177 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Hamiltonicity of Sparse Pseudorandom Graphs Ferber, Asaf Han, Jie Mao, Dingjia Vershynin, Roman Combinatorics We show that every $(n,d,λ)$-graph contains a Hamilton cycle for sufficiently large $n$, assuming that $d\geq \log^{6}n$ and $λ\leq cd$, where $c=\frac{1}{70000}$. This significantly improves a recent result of Glock, Correia and Sudakov, who obtained a similar result for $d$ that grows polynomially with $n$. The proof is based on a new result regarding the second largest eigenvalue of the adjacency matrix of a subgraph induced by a random subset of vertices, combined with a recent result on connecting designated pairs of vertices by vertex-disjoint paths in $(n,d,λ)$-graphs. We believe that the former result is of independent interest and will have further applications. |
| title | Hamiltonicity of Sparse Pseudorandom Graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2402.06177 |