A dirac-type theorem for berge cycles in random hypergraphs

2020/09/30 by Clemens, Dennis, Ehrenmüller, Julia, Person, Yury
#Mathematik

paper · doi:10.15480/882.2946

Abstract

A Hamilton Berge cycle of a hypergraph on n vertices is an alternating se-quence (v1, e1, v2, …, vn, en) of distinct vertices v1, …, vn and distinct hyperedges e1, …, en such that (Formula Presented) and (Formula Presented) for every i ∈ [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 ≥ 3, every real γ > 0 and p ≥ln17rnr−1n asymptotically almost surely, (every)spanning(r−1) subgraph (Formula Presented)) with minimum vertex degree δ1(H) ≥2r−11 + γ pn contains a Hamilton Berge cycle. The minimum degree condition is asymptotically tight and the bound on p is optimal up to some polylogarithmic factor.

Related

• A Dirac-type theorem for Berge cycles in random hypergraphs
• Dirac's Theorem for hamiltonian Berge cycles in uniform hypergraphs
• A hypergraph analog of Dirac's Theorem for long cycles in 2-connected graphs
• Pósa-type results for Berge-hypergraphs
• Berge Hamilton cycles in a random sparsification of dense hypergraphs