The threshold for powers of tight Hamilton cycles in random hypergraphs (Q6972372)

The \(k\)-th power of an \(r\)-uniform cycle is the \(r\)-uniform graph obtained from a cyclic ordering of its vertices, where every \(r\)-set of vertices all of which are at cyclic distance at most \(k\) apart, must form an edge. Equivalently, it can be formed by pasting \(k\)-vertex complete \(r\)-graphs in a cyclic fashion. The authors study the threshold \(p = p(k,r,n)\) which ensures the existence, with high probability, of a Hamilton (vertex-spanning) \(k\)-th power of an \(r\)-uniform cycle in the binomial random \(n\)-vertex \(r\)-graph \(H^{(r)}(n,p)\), i.e., the \(n\)-vertex random \(r\)-graph where every edge appears independently with probability \(p\).\N\NA first-moment calculation shows that for a small constant \(c\) and \(p = cn^{-1/\binom{k+r-2}{r-2}}\), with high probability \(H^{(r)}(n,p)\) does not contain a Hamilton \(k\)-th power of an \(r\)-uniform cycle. The main result of the authors is that the property of containing such a cycle has a ``semi-sharp'' threshold, i.e., the authors show the existence of an explicit constant \(C = C(k,r)\) such that for \(p = Cn^{-1/\binom{k+r-2}{r-2}}\), with high probability \(H^{(r)}(n,p)\) contains a Hamilton \(k\)-th power of an \(r\)-uniform cycle. A previous result by \textit{O. Parczyk} and \textit{Y. Person} [Random Struct. Algorithms 49, No. 4, 819--844 (2016; Zbl 1352.05139)] implied a weaker version of this last result, with the same conclusion but requiring instead that \(p n^{1/\binom{k+r-2}{r-2}}\) tends to infinity.\N\NThe proof proceeds by adapting a proof strategy of \textit{B. Narayanan} and \textit{M. Schacht} [ibid. 57, No. 1, 244--255 (2020; Zbl 1472.05088)] and combines a second-moment argument (via the Paley-Zygmund inequality) together with a ``sharp threshold'' argument by \textit{E. Friedgut} [ibid. 26, No. 1--2, 37--51 (2005; Zbl 1059.05092)].