Non-linear Hamilton cycles in linear quasi-random hypergraphs

A k-graph H is called (p, μ)-dense if for all not necessarily disjoint sets A1, …, Ak ⊆ V(H) we have e(A1, …, Ak) ≥ p|A1| ⃛ |Ak| – μ|V(H)|k. This is believed to be the weakest form of quasi-randomness in k-graphs and also known as linear quasi-randomness. In this paper we show that for ℓ < k satisfying (k – ℓ) ∤ k, (p, μ)-denseness plus a minimum (ℓ + 1)-vertex-degree αnk–ℓ–1 guarantees Hamilton ℓ-cycles, but requiring a minimum ℓ-vertex-degree Ω(nk–ℓ) instead is not sufficient. This answers a question of Lenz–Mubayi–Mycroft and characterizes the triples (k, ℓ, d) such that degenerate choices of p and α force ℓ-Hamiltonicity. We actually prove a general result on ℓ-Hamiltonicity in quasi-random k-graphs, assuming a minimum vertex degree and essentially that every two ℓ-sets can be connected by a constant length ℓ-path. This result reduces the ℓ-Hamiltonicity problem to the study of the connection property. Moreover, we note that our proof can be turned into a deterministic polynomial-time algorithm that outputs the Hamilton ℓ-cycle. Our proof uses the lattice-based absorption method in the non-standard way and is the first one that embeds a nonlinear Hamilton cycle in linear quasi-random k-graphs.