On the strength of connectedness of a random hypergraph

Abstract

Bollobás and Thomason (1985) proved that for each $k=k(n)\in [1,n-1]$, with high probability, the random graph process, where edges are added to vertex set $V=[n]$ uniformly at random one after another, is such that the stopping time of having minimal degree $k$ is equal to the stopping time of becoming $k$-(vertex-)connected. We extend this result to the $d$-uniform random hypergraph process, where $k$ and $d$ are fixed. Consequently, for $m=\frac{n}{d}(\ln n+(k-1)\ln \ln n+c)$ and $p=(d-1)!\frac{\ln n+(k-1)\ln \ln n+c}{n^{d-1}}$, the probability that the random hypergraph models $H_d(n,m)$ and $H_d(n,p)$ are $k$-connected tends to $e^{-e^{-c}/(k-1)!}.$

16 pages, minor revisions from first draft