On Weak Hamiltonicity of a Random Hypergraph

Original · EN

A weak (Berge) cycle is an alternating sequence of vertices and (hyper)edges C=(v₀, e₁, v₁,..., vℓ₋₁, eℓ, vℓ=v₀) such that the vertices v₀,..., vℓ₋₁ are distinct with vₖ, vₖ₊₁ ∈ eₖ for each k, but the edges e₁,..., 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)! n + cnᵈ⁻¹, the probability that Hd(n, p) has a weak Hamilton cycle tends to e⁻ᵉ⁻ᶜ, 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(n + c)/d), where m potential edges are chosen uniformly at random to be present, is weak Hamiltonian also tends to e⁻ᵉ⁻ᶜ.