On the strength of connectedness of a random hypergraph

2014/09/04 by Poole, Daniel
#Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.1409.1489

Abstract

Bollobás and Thomason (1985) proved that for each k=k(n) ∈ [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=(n)/(d)(ln n +(k-1)ln ln n +c) and p=(d-1)! \fracln n + (k-1) ln ln n +cn^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)!.

Related

• Threshold and hitting time for high-order connectivity in random hypergraphs
• Largest components in random hypergraphs
• Acquaintance time of random graphs near connectivity threshold
• Minimum degree k and k-connectedness usually arrive together
• Critical random hypergraphs: The emergence of a giant set of identifiable vertices