On the strength of connectedness of a random hypergraph

Daniel Poole¹

¹The Ohio State University

The electronic journal of combinatorics, Tome 22 (2015) no. 1

Résumé

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)!}.$

Détail

DOI : 10.37236/4666

Classification : 05C80, 05C65, 05C40, 60C05
Mots-clés : random hypergraph, vertex connectivity