Resilience for tight Hamiltonicity

Abstract

We prove that random hypergraphs are asymptotically almost surely resiliently Hamiltonian. Specifically, for any gamma > 0 and k >= 3, we show that asymptotically almost surely, every subgraph of the binomial random h-uniform hypergraph G((k))(n, n(gamma-1)) in which all (h-1)-sets are contained in at least (1/2 + 2 gamma)pn edges has a tight Hamilton cycle. This is a cyclic ordering of the n vertices such that each consecutive h vertices forms an edge.