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 \geq \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) \geq \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.
@article{10_37236_8611,
author = {Dennis Clemens and Julia Ehrenm\"uller and Yury Person},
title = {A {Dirac-type} theorem for {Berge} cycles in random hypergraphs},
journal = {The electronic journal of combinatorics},
year = {2020},
volume = {27},
number = {3},
doi = {10.37236/8611},
zbl = {1466.05194},
url = {http://geodesic.mathdoc.fr/articles/10.37236/8611/}
}
TY - JOUR
AU - Dennis Clemens
AU - Julia Ehrenmüller
AU - Yury Person
TI - A Dirac-type theorem for Berge cycles in random hypergraphs
JO - The electronic journal of combinatorics
PY - 2020
VL - 27
IS - 3
UR - http://geodesic.mathdoc.fr/articles/10.37236/8611/
DO - 10.37236/8611
ID - 10_37236_8611
ER -
%0 Journal Article
%A Dennis Clemens
%A Julia Ehrenmüller
%A Yury Person
%T A Dirac-type theorem for Berge cycles in random hypergraphs
%J The electronic journal of combinatorics
%D 2020
%V 27
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/8611/
%R 10.37236/8611
%F 10_37236_8611
Dennis Clemens; Julia Ehrenmüller; Yury Person. A Dirac-type theorem for Berge cycles in random hypergraphs. The electronic journal of combinatorics, Tome 27 (2020) no. 3. doi: 10.37236/8611
