Resilience of rainbow Hamilton cycles in pseudorandom graphs
Abstract
We prove that every spanning subgraph H of an n-vertex (p,β)-bijumbled graph, satisfying δ(H)≥(1/2+ε)pn, where ε > 0 is arbitrarily small yet fixed, admits a rainbow Hamilton cycle under any globally μpn-bounded colouring, provided that β≤ cpn and pn≥ M, where μ, c, and M are positive constants depending solely on ε; in particular, pn may be taken to be a sufficiently large constant. This answers a question of Coulson, Keevash, Perarnau and Yepremyan for random graphs and extends it to deterministic pseudorandom hosts. In fact, we prove that H admits at least (apn)n rainbow Hamilton cycles, where a > 0 is a constant depending solely on ε. If pn≥ Dlog n, then, upon fixing a coloured H, retaining each edge independently with probability Dlog n/(pn) preserves rainbow Hamiltonicity asymptotically almost surely. The logarithmic degree requirement is needed only for this percolation conclusion. All three conclusions also hold with rainbowness replaced by avoidance of prescribed pairs of edges, provided that each edge has at most μpn conflicting partners. Our proofs use spread measures and the lopsided local lemma.
Related
- Rainbow spanning configurations in uniformly coloured pseudorandom graphs
- Exact-palette rainbow embeddings in uniformly coloured pseudorandom graphs
- Long induced cycles in pseudorandom graphs
- On Hamilton cycles in quasiprimitive graphs of order 2pq
- On the Minimum Number of Hamilton Cycles in Hamiltonian Threshold Graphs: A Simple Proof
BibTeX
@misc{aignerhorev2026resilience,
title = {{Resilience of rainbow Hamilton cycles in pseudorandom graphs}},
author = {Elad Aigner-Horev and Dan Hefetz and Yury Person},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.26655},
eprint = {2609.26655},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.26655},
}
RIS
TY - UNPB
TI - Resilience of rainbow Hamilton cycles in pseudorandom graphs
AU - Elad Aigner-Horev
AU - Dan Hefetz
AU - Yury Person
PY - 2026
DA - 2026/10/21
PB - arXiv
DO - 10.48550/arxiv.2609.26655
UR - https://arxiv.org/abs/2609.26655
AB - We prove that every spanning subgraph H of an n-vertex (p,β)-bijumbled graph, satisfying δ(H)≥(1/2+ε)pn, where ε > 0 is arbitrarily small yet fixed, admits a rainbow Hamilton cycle under any globally μpn-bounded colouring, provided that β≤ cpn and pn≥ M, where μ, c, and M are positive constants depending solely on ε; in particular, pn may be taken to be a sufficiently large constant. This answers a question of Coulson, Keevash, Perarnau and Yepremyan for random graphs and extends it to deterministic pseudorandom hosts. In fact, we prove that H admits at least (apn)^n rainbow Hamilton cycles, where a > 0 is a constant depending solely on ε. If pn≥ Dlog n, then, upon fixing a coloured H, retaining each edge independently with probability Dlog n/(pn) preserves rainbow Hamiltonicity asymptotically almost surely. The logarithmic degree requirement is needed only for this percolation conclusion. All three conclusions also hold with rainbowness replaced by avoidance of prescribed pairs of edges, provided that each edge has at most μpn conflicting partners. Our proofs use spread measures and the lopsided local lemma.
ER -