2014/10/27 by Daniel Poole, Daniel J. Poole, Poole, Daniel · 2 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Graph theory and applications #Limits and Structures in Graph Theory #math.CO #math.PR
paper · pdf · doi:10.48550/arxiv.1410.7446
25 pages
arxiv created 2014/10/27 · arxiv updated 2014/10/29
A \it weak (Berge) cycle is an alternating sequence of vertices and (hyper)edges C=(v0, e1, v1, ..., vℓ-1, e_ℓ, vℓ=v0) such that the vertices v0, ..., vℓ-1 are distinct with vk, vk+1 ∈ ek for each k, but the edges e1, ..., e_ℓ are not necessarily distinct. We prove that the main barrier to the random d-uniform hypergraph Hd(n,p), where each of the potential edges of cardinality d is present with probability p, developing a weak Hamilton cycle is the presence of isolated vertices. In particular, for d ≥ 3 fixed and p=(d-1)! \fracln n + cnd-1, the probability that Hd(n, p) has a weak Hamilton cycle tends to e^-e-c, which is also the limiting probability that Hd(n,p) has no isolated vertices. As a consequence, the probability that the random hypergraph Hd(n, m=(n(ln n + c))/(d)), where m potential edges are chosen uniformly at random to be present, is weak Hamiltonian also tends to e^-e-c.