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  
Ehrenmüller, Julia 
Person, Yury 
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.
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

Page view(s)

Last Week
Last month
checked on Jul 5, 2022


Last Week
Last month
checked on Jun 30, 2022

Google ScholarTM


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.