On the strength of connectedness of a random hypergraph

preprint2015arXivOpen access

Abstract

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

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.