Inheritance of expansion and oriented Hamilton cycles in robust expanders: a regularity-free proof
Abstract
Häggkvist and Thomason proved that every n-vertex oriented graph with minimum semidegree at least (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 (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 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.
Related
- Maximal Regularity and Existence for Superquadratic Parabolic Hamilton--Jacobi Equations: The Endpoint case
- Endpoint Maximal Regularity for Superquadratic Hamilton-Jacobi Equations and Applications to Ergodic Mean-field Games Systems
- Improved Regularity for Nonlocal Hamilton--Jacobi Equations with Superlinear Hamiltonians
- C^(sigma+alpha) regularity for fractional Hamilton-Jacobi equations, and rates of convergence in periodic homogenization
- Regularity of the Time-to-Collision Map and Convergence of Learned Hamilton-Jacobi Solutions
BibTeX
@misc{debiasio2026inheritance,
title = {{Inheritance of expansion and oriented Hamilton cycles in robust expanders: a regularity-free proof}},
author = {Louis DeBiasio},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.09072},
eprint = {2610.09072},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.09072},
}
RIS
TY - UNPB
TI - Inheritance of expansion and oriented Hamilton cycles in robust expanders: a regularity-free proof
AU - Louis DeBiasio
PY - 2026
DA - 2026/10/06
PB - arXiv
DO - 10.48550/arxiv.2610.09072
UR - https://arxiv.org/abs/2610.09072
AB - Häggkvist and Thomason proved that every n-vertex oriented graph with minimum semidegree at least (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 (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 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.
ER -