Evolution of high-order connected components in random hypergraphs

Abstract

We consider high-order connectivity in $k$-uniform hypergraphs defined as follows: Two $j$-sets are $j$-connected if there is a walk of edges between them such that two consecutive edges intersect in at least $j$ vertices. We describe the evolution of $j$-connected components in the $k$-uniform binomial random hypergraph ${\mathcal{H}}^k(n,p)$. In particular, we determine the asymptotic size of the giant component shortly after its emergence and establish the threshold at which the ${\mathcal{H}}^k(n,p)$ becomes $j$-connected with high probability. We also obtain a hitting time result for the related random hypergraph process $\{{\mathcal{H}}^k(n,M){\}}_M$ -- the hypergraph becomes $j$-connected exactly at the moment when the last isolated $j$-set disappears. This generalises well-known results for graphs and vertex-connectivity in hypergraphs.

Extended abstract presented at the European Conference on Combinatorics, Graph Theory and Applications 2015 summarising the results of arXiv:1501.07835 and arXiv:1502.07289, 6 pages

References in corpus (2)

• The size of the giant component in random hypergraphs
• Threshold and hitting time for high-order connectivity in random hypergraphs

Cited by in corpus (4)

• Hypergraph Spectral Clustering in the Weighted Stochastic Block Model
• Stochastic Block Model for Hypergraphs: Statistical limits and a semidefinite programming approach
• Robust Hypergraph Clustering via Convex Relaxation of Truncated MLE
• Parallel Algorithms and Heuristics for Efficient Computation of High-Order Line Graphs of Hypergraphs