Metraipolis › archive › dc_ccf4f0cdb549
Inheritance of expansion and oriented Hamilton cycles in robust expanders: a regularity-free proof — arXiv:2610.09072
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.09072
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-08T12:43:51.243Z
- SHA-256 of the archived text
88ef1cc4fc4eb4cfd2ea09872b17bb8ef79c3910ae44f5d93953ddf2bdbaddd7- Stable URL of this page
https://metraipolis.com/documento/dc_ccf4f0cdb549
How to cite
Inheritance of expansion and oriented Hamilton cycles in robust expanders: a regularity-free proof — arXiv:2610.09072 — arXiv (en), https://arxiv.org/abs/2610.09072 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_ccf4f0cdb549 (Metraipolis archive dc_ccf4f0cdb549, sha256 88ef1cc4fc4eb4cfd2ea09872b17bb8ef79c3910ae44f5d93953ddf2bdbaddd7)
BibTeX
@misc{dcccf4f0cdb549,
title = {Inheritance of expansion and oriented Hamilton cycles in robust expanders: a regularity-free proof — arXiv:2610.09072},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.09072},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_ccf4f0cdb549; sha256 88ef1cc4fc4eb4cfd2ea09872b17bb8ef79c3910ae44f5d93953ddf2bdbaddd7},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.09072. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Häggkvist and Thomason proved that every $n$-vertex oriented graph with minimum semidegree at least $(\frac{5}{12}+o(1))n$ contains every orientation of a Hamilton cycle. Using Szemerédi's regularity lemma, Kelly later improved this to the asymptotically sharp bound $(\frac{3}{8}+o(1))n$. Taylor subsequently generalized Kelly's theorem by proving that every sufficiently large robust outexpander with linear minimum semidegree contains every orientation of a Hamilton cycle. We revisit Häggkvist and Thomason's proof and show that it can be modified to give a regularity-free proof of Taylor's theorem (and thus Kelly's theorem). Building on this, we also give regularity-free proofs of related results on Hamilton-connectivity and linkage in robust outexpanders. As applications of these results, we are able to replace the use of the regularity lemma in known results on arbitrary orientations of Hamilton cycles in $n$-vertex digraphs with minimum semidegree at least $\frac{n}{2}$ and in $n$-vertex digraphs with minimum total degree at least $(1+o(1))n$. The first step is to show that, in an $n$-vertex robust outexpander with linear minimum semidegree, two uniformly chosen disjoint sets of logarithmic size satisfy Hall's condition with high probability. The second is to show that robust expansion is inherited by uniformly chosen linear sized sets. In both cases, we use the graph-container methods of Kleitman--Winston and Sapozhenko to reduce the possible obstructions to a small enough family to permit a union bound.
Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.CO, nuovi lavori del giorno).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2610.09072 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-08T12:17:00.175Z dalla pagina https://arxiv.org/list/math.CO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).