2019/03/21 by Clemens, Dennis, Ehrenmüller, Julia, Person, Yury
#05C45 #05C65 #05C80 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1903.09057
A Hamilton Berge cycle of a hypergraph on n vertices is an alternating sequence (v1, e1, v2, …, vn, en) of distinct vertices v1, …, vn and distinct hyperedges e1, …, en such that \v1,vn\⊆ en and \vi, vi+1\ ⊆ ei 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 ≥ \fracln17r nnr-1 asymptotically almost surely, every spanning subgraph H ⊆ H(r)(n,p) with minimum vertex degree δ1(H) ≥ (\frac12r-1 + γ) p \binomnr-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.