A Dirac-type theorem for Berge cycles in random hypergraphs

Abstract

A Hamilton Berge cycle of a hypergraph on $n$ vertices is an alternating sequence $(v_1,e_1,v_2,\dots ,v_n,e_n)$ of distinct vertices $v_1,\dots ,v_n$ and distinct hyperedges $e_1,\dots ,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\ge 3$, every real $\gamma >0$ and $p\ge \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)\ge \left(\frac{1}{2^{r-1}}+\gamma \right)p\left(\genfrac{}{}{0ex}{}{n}{r-1}\right)$ contains a Hamilton Berge cycle. The minimum degree condition is asymptotically tight and the bound on $p$ is optimal up to some polylogarithmic factor.

16 pages, an extended abstract of this paper appeared in the Proceedings of the Discrete Mathematics Days 2016