On Weak Hamiltonicity of a Random Hypergraph

Abstract

A {\it weak (Berge) cycle} is an alternating sequence of vertices and (hyper)edges $C=(v_0,e_1,v_1,...,v_{\ell -1},e_{\ell },v_{\ell }=v_0)$ such that the vertices $v_0,...,v_{\ell -1}$ are distinct with $v_k,v_{k+1}\in e_k$ for each $k$, but the edges $e_1,...,e_{\ell }$ are not necessarily distinct. We prove that the main barrier to the random $d$-uniform hypergraph $H_d(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\ge 3$ fixed and $p=(d-1)!\frac{\ln n+c}{n^{d-1}}$, the probability that $H_d(n,p)$ has a weak Hamilton cycle tends to $e^{-e^{-c}}$, which is also the limiting probability that $H_d(n,p)$ has no isolated vertices. As a consequence, the probability that the random hypergraph $H_d(n,m=\frac{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}}$.

25 pages

Cited by in corpus (1)

• On offset Hamilton cycles in random hypergraphs