Resilience of rainbow Hamilton cycles in pseudorandom graphs

Source abstract

For every fixed $\varepsilon\in(0,1/2)$, we prove that every spanning subgraph $H$ of an $n$-vertex $(p,β)$-bijumbled graph satisfying $δ(H)\geq(1/2+\varepsilon)pn$ contains a rainbow Hamilton cycle under every globally $μpn$-bounded colouring, provided $β\leq cpn$ and $pn\geq M$ both hold. The same assertion holds under the relative condition $°_H(v)\geq(1/2+\varepsilon)°_G(v)$ for every vertex $v$, provided $δ(G)\geq(1-\varepsilon/4)pn$ holds. Under either degree condition, there are at least $(apn)^n$ such cycles. Here, $c,μ,a,M>0$ depend only on $\varepsilon$; in particular, $pn$ may be a sufficiently large constant. If $pn\geq D\log n$, then, upon fixing a coloured $H$, retaining each edge independently with probability $D\log n/(pn)$ preserves rainbow Hamiltonicity asymptotically almost surely. The logarithmic degree requirement is needed only for this percolation conclusion. The existence theorem answers a problem of Coulson, Keevash, Perarnau and Yepremyan for random graphs and extends it to deterministic pseudorandom hosts. In fact, all three conclusions hold with rainbowness replaced by avoidance of prescribed pairs of edges; each edge having at most $μpn$ conflicting partners. We construct an $O(1/(pn))$-spread probability measure on conflict-free Hamilton cycles; this then yields the enumeration and percolation results.