Non-linear Hamilton cycles in linear quasi-random hypergraphs

A k-graph H is called (p, µ)-dense if for all not necessarily disjoint sets A₁,..., A_k ⊆ V (H) we have e(A₁,..., A_k) ≥ p|A₁|· · · |A_k| − µ|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 l < k satisfying (k − l) - k, (p, µ)-denseness plus a minimum (l + 1)-vertex-degree αn^k−l−1 guarantees Hamilton l-cycles, but requiring a minimum l-vertex-degree Ω(n^k−l) instead is not sufficient. This answers a question of Lenz-Mubayi-Mycroft and characterizes the triples (k, l, d) such that degenerate choices of p and α force l-Hamiltonicity. We actually prove a general result on l-Hamiltonicity in quasi-random k-graphs, assuming a minimum vertex degree and essentially that every two l-sets can be connected by a constant length l-path. This result reduces the l-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 l-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.