TY - JOUR

T1 - A threshold result for loose Hamiltonicity in random regular uniform hypergraphs

AU - Altman, Daniel

AU - Greenhill, Catherine

AU - Isaev, Mikhail

AU - Ramadurai, Reshma

PY - 2020/5

Y1 - 2020/5

N2 - Let G(n,r,s) denote a uniformly random r-regular s-uniform hypergraph on n vertices, where s is a fixed constant and r=r(n) may grow with n. An ℓ-overlapping Hamilton cycle is a Hamilton cycle in which successive edges overlap in precisely ℓ vertices, and 1-overlapping Hamilton cycles are called loose Hamilton cycles. When r,s≥3 are fixed integers, we establish a threshold result for the property of containing a loose Hamilton cycle. This partially verifies a conjecture of Dudek, Frieze, Ruciński and Šileikis (2015). In this setting, we also find the asymptotic distribution of the number of loose Hamilton cycles in G(n,r,s). Finally we prove that for ℓ=2,…,s−1 and for r growing moderately as n→∞, the probability that G(n,r,s) has a ℓ-overlapping Hamilton cycle tends to zero.

AB - Let G(n,r,s) denote a uniformly random r-regular s-uniform hypergraph on n vertices, where s is a fixed constant and r=r(n) may grow with n. An ℓ-overlapping Hamilton cycle is a Hamilton cycle in which successive edges overlap in precisely ℓ vertices, and 1-overlapping Hamilton cycles are called loose Hamilton cycles. When r,s≥3 are fixed integers, we establish a threshold result for the property of containing a loose Hamilton cycle. This partially verifies a conjecture of Dudek, Frieze, Ruciński and Šileikis (2015). In this setting, we also find the asymptotic distribution of the number of loose Hamilton cycles in G(n,r,s). Finally we prove that for ℓ=2,…,s−1 and for r growing moderately as n→∞, the probability that G(n,r,s) has a ℓ-overlapping Hamilton cycle tends to zero.

KW - Hamilton cycle

KW - Hypergraph

KW - Random hypergraph

KW - Threshold

UR - http://www.scopus.com/inward/record.url?scp=85075403063&partnerID=8YFLogxK

U2 - 10.1016/j.jctb.2019.11.001

DO - 10.1016/j.jctb.2019.11.001

M3 - Article

AN - SCOPUS:85075403063

SN - 0095-8956

VL - 142

SP - 307

EP - 373

JO - Journal of Combinatorial Theory, Series B

JF - Journal of Combinatorial Theory, Series B

ER -