The threshold for powers of tight Hamilton cycles in random hypergraphs
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)].
- Dirac-type questions for hypergraphs -- a survey (or more problems for Endre to solve)
- Hamiltonian circuits in random graphs
- scientific article; zbMATH DE number 3632537 (Why is no real title available?)
- scientific article; zbMATH DE number 1540669 (Why is no real title available?)
- Hunting for sharp thresholds
- Limit distribution for the existence of Hamiltonian cycles in a random graph
- Loose Hamilton cycles in random 3-uniform hypergraphs
- On Pósa's conjecture for random graphs
- Powers of Hamilton cycles in random graphs and tight Hamilton cycles in random hypergraphs
- Powers of tight Hamilton cycles in randomly perturbed hypergraphs
- Recent advances on Dirac-type problems for hypergraphs
- Reducibility among combinatorial problems
- Sharp thresholds for nonlinear Hamiltonian cycles in hypergraphs
- Some Theorems on Abstract Graphs
- Spanning structures and universality in sparse hypergraphs
- Spanning Subgraphs of Random Graphs
- The threshold for the square of a Hamilton cycle
- Tight Hamilton cycles in random uniform hypergraphs
- Triangle resilience of the square of a Hamilton cycle in random graphs
This page was built for publication: The threshold for powers of tight Hamilton cycles in random hypergraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6972372)
