Verlagslink DOI: 10.1016/j.endm.2016.09.032
Titel: A Dirac-type theorem for Hamilton Berge cycles in random hypergraphs
Sprache: Englisch
Autor/Autorin: Clemens, Dennis  
Ehrenmüller, Julia 
Person, Yury 
Schlagwörter: Berge cycles; Dirac's theorem; Random hypergraphs; resilience
Erscheinungs­datum: 1-Okt-2016
Quellenangabe: Electronic Notes in Discrete Mathematics (54): 181-186 (2016-10-01)
Zusammenfassung (englisch): 
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
Zeitschrift: Electronic notes in discrete mathematics 
Institut: Mathematik E-10 
Dokumenttyp: Artikel/Aufsatz
Enthalten in den Sammlungen:Publications without fulltext

Zur Langanzeige

Seitenansichten

182
Letzte Woche
1
Letzten Monat
2
checked on 01.10.2022

SCOPUSTM   
Zitate

6
Letzte Woche
0
Letzten Monat
0
checked on 30.06.2022

Google ScholarTM

Prüfe

Volltext ergänzen

Feedback zu diesem Datensatz

Diesen Datensatz zitieren

Export

Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.