On Weak Hamiltonicity of a Random Hypergraph

preprint2014arXivOpen access

Abstract

A {\it weak (Berge) cycle} is an alternating sequence of vertices and (hyper)edges C=(v0,e1,v1,...,vℓ−1,eℓ,vℓ=v0)C=(v_0, e_1, v_1, ..., v_{\ell-1}, e_\ell, v_{\ell}=v_0) such that the vertices v0,...,vℓ−1v_0, ..., v_{\ell-1} are distinct with vk,vk+1∈ekv_k, v_{k+1} \in e_{k} for each kk, but the edges e1,...,eℓe_1, ..., e_\ell are not necessarily distinct. We prove that the main barrier to the random dd-uniform hypergraph Hd(n,p),H_d(n,p), where each of the potential edges of cardinality dd is present with probability pp, developing a weak Hamilton cycle is the presence of isolated vertices. In particular, for d≥3d \geq 3 fixed and p=(d−1)!ln⁡n+cnd−1p=(d-1)! \frac{\ln n + c}{n^{d-1}}, the probability that Hd(n,p)H_d(n, p) has a weak Hamilton cycle tends to e−e−ce^{-e^{-c}}, which is also the limiting probability that Hd(n,p)H_d(n,p) has no isolated vertices. As a consequence, the probability that the random hypergraph Hd(n,m=n(ln⁡n+c)d),H_d(n, m=\frac{n(\ln n + c)}{d}), where mm potential edges are chosen uniformly at random to be present, is weak Hamiltonian also tends to e−e−ce^{-e^{-c}}.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.