Publication details
Non-linear Hamilton cycles in linear quasi-random hypergraphs
| Authors | |
|---|---|
| Year of publication | 2021 |
| Type | Article in Proceedings |
| Conference | PROCEEDINGS OF THE THIRTY-SECOND ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS (SODA'21) |
| Citation | |
| Doi | http://dx.doi.org/10.1137/1.9781611976465.6 |
| Description | 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 l < k satisfying (k – l) ? k, (p, µ)-denseness plus a minimum (l + 1)-vertex-degree ?nk–l–1 guarantees Hamilton l-cycles, but requiring a minimum l-vertex-degree ?(nk–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. |