A Dirac-type theorem for Hamilton Berge cycles in random hypergraphs

详细信息    查看全文

• 作者：Dennis Clemens^a ; ^{dennis.clemens@tuhh.de" class="auth_mail" title="E-mail the corresponding author} ; Julia Ehrenmü ; ller^a ; ^{julia.ehrenmueller@tuhh.de" class="auth_mail" title="E-mail the corresponding author} ; Yury Person^b ; ¹ ; ^{person@math.uni-frankfurt.de" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Random hypergraphs ; Berge cycles ; Dirac's theorem ; resilience
• 刊名：Electronic Notes in Discrete Mathematics
• 出版年：2016
• 出版时间：October 2016
• 年：2016
• 卷：54
• 期：Complete
• 页码：181-186
• 全文大小：191 K

文摘

A Hamilton Berge cycle of a hypergraph on n   vertices is an alternating sequence (v₁,e₁,v₂,…,v_n,e_n$v_1,e_1,v_2,\dots ,v_n,e_n$) of distinct vertices v₁,…,v_n$v_1,\dots ,v_n$ and distinct hyperedges e₁,…,e_n$e_1,\dots ,e_n$ such that {v₁,v_n}⊆e_n$\{v_1,v_n\}\subseteq e_n$ and {v_i,v_i+1}⊆e_i$\{v_i,v_{i+1}\}\subseteq e_i$ for every i∈[n−1]$i\in [n-1]$. We prove a Dirac-type theorem for Hamilton Berge cycles in random r  -uniform hypergraphs by showing that for every integer r≥3$r\ge 3$ there exists k=k(r)$k=k(r)$ such that for every γ>0$\gamma >0$ and $p\ge \frac{{\log }^{k(r)}(n)}{nr-1}$ asymptotically almost surely every spanning subhypergraph H⊆H^(r)(n,p)$H\subseteq H^{(r)}(n,p)$ with minimum vertex degree ${\delta }_1(H)\ge (\frac{1}{2^{r-1}+\gamma })p\left(\begin{array}{c}n-1\\ r-1\end{array}\right)$ contains a Hamilton Berge cycle. The minimum degree condition is asymptotically tight and the bound on p   is optimal up to possibly the logarithmic factor. As a corollary this gives a new upper bound on the threshold of H^(r)(n,p)$H^{(r)}(n,p)$ with respect to Berge Hamiltonicity.