A Dirac-type theorem for Berge cycles in random hypergraphs (Q2194091): Difference between revisions

Summary: A Hamilton Berge cycle of a hypergraph on \(n\) vertices is an alternating sequence \((v_1, e_1, v_2, \ldots, v_n, e_n)\) of distinct vertices \(v_1, \ldots, v_n\) and distinct hyperedges \(e_1, \ldots, e_n\) such that \(\{v_1,v_n\}\subseteq e_n\) and \(\{v_i, v_{i+1}\} \subseteq e_i\) for every \(i\in [n-1]\). We prove the following Dirac-type theorem about Berge cycles in the binomial random \(r\)-uniform hypergraph \(H^{(r)}(n,p)\): for every integer \(r \geq 3\), every real \(\gamma>0\) and \(p \geqslant \frac{\ln^{17r} n}{n^{r-1}}\) asymptotically almost surely, every spanning subgraph \(H \subseteq H^{(r)}(n,p)\) with minimum vertex degree \(\delta_1(H) \geqslant \left(\frac{1}{2^{r-1}} + \gamma\right) p \binom{n}{r-1}\) contains a Hamilton Berge cycle. The minimum degree condition is asymptotically tight and the bound on \(p\) is optimal up to some polylogarithmic factor.