Please use this identifier to cite or link to this item:
Publisher DOI: 10.37236/8611
Title: A dirac-type theorem for berge cycles in random hypergraphs
Language: English
Authors: Clemens, Dennis  
Ehrenmüller, Julia 
Person, Yury 
Issue Date: 21-Aug-2020
Publisher: EMIS ELibEMS
Source: Electronic Journal of Combinatorics 3 (27): 3.39, 1-23 (2020)
Journal or Series Name: The electronic journal of combinatorics 
Abstract (english): 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.
DOI: 10.15480/882.2946
ISSN: 1077-8926
Institute: Mathematik E-10 
Type: (wissenschaftlicher) Artikel
Funded by: YP was supported by DFG grant PE 2299/1-1.
License: CC BY-ND 4.0 (Attribution-NoDerivatives) CC BY-ND 4.0 (Attribution-NoDerivatives)
Appears in Collections:Publications with fulltext

Files in This Item:
File Description SizeFormat
8611-PDF file-33188-1-10-20200814.pdfVerlags-PDF402,1 kBAdobe PDFThumbnail
Show full item record

Page view(s)

Last Week
Last month
checked on Nov 28, 2020


checked on Nov 28, 2020

Google ScholarTM


Note about this record


This item is licensed under a Creative Commons License Creative Commons