|Publisher DOI:||10.1016/j.endm.2016.09.032||Title:||A Dirac-type theorem for Hamilton Berge cycles in random hypergraphs||Language:||English||Authors:||Clemens, Dennis
|Keywords:||Berge cycles; Dirac's theorem; Random hypergraphs; resilience||Issue Date:||1-Oct-2016||Source:||Electronic Notes in Discrete Mathematics (54): 181-186 (2016-10-01)||Abstract (english):||
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 a Dirac-type theorem for Hamilton Berge cycles in random r-uniform hypergraphs by showing that for every integer r≥3 there exists k=k(r) such that for every γ>0 and p≥logk(r)(n)nr−1 asymptotically almost surely every spanning subhypergraph H⊆H(r)(n,p) with minimum vertex degree δ1(H)≥(12r−1+γ)p(n−1r−1) 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) with respect to Berge Hamiltonicity.
|URI:||http://hdl.handle.net/11420/5765||ISSN:||1571-0653||Journal:||Electronic notes in discrete mathematics||Institute:||Mathematik E-10||Document Type:||Article|
|Appears in Collections:||Publications without fulltext|
Show full item record
checked on Jul 5, 2022
checked on Jun 30, 2022
Add Files to Item
Note about this record
Cite this record
Items in TORE are protected by copyright, with all rights reserved, unless otherwise indicated.