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 $(\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.

The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.

More in Computational Complexity

• arXiv preprint · 6 October 2026

  Perfect state transfer on mixed graphs: complete classes and transfer times

  Xingkun Song
• arXiv preprint · 7 October 2026

  A deterministic algorithm for signing bipartite graphs at the Ramanujan bound

  Zhiqiang Xu
• arXiv preprint · 6 October 2026

  On the complexity of the single-move labeled token routing problem

  Nicolas Bousquet, Remy El Sabeh, Amer E. Mouawad and 1 other
• arXiv preprint · 7 October 2026

  Moment Methods for Uniform Average Mixing on Strongly Regular Graphs

  Musung Kang
• OpenAlex · 6 October 2026

  Stability of plethysm coefficients and modified polynomial induction

  Soumyadip Sarkar

All new papers in Computational Complexity