pith. sign in

arxiv: 1502.07289 · v1 · pith:U3GZ27I7new · submitted 2015-02-25 · 🧮 math.CO

Threshold and hitting time for high-order connectivity in random hypergraphs

classification 🧮 math.CO
keywords connectedhypergraphrandombecomesconnectivityedgeshittinghypergraphs
0
0 comments X
read the original abstract

We consider the following definition of connectivity in $k$-uniform hypergraphs: 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 determine the threshold at which the random $k$-uniform hypergraph with edge probability $p$ becomes $j$-connected with high probability. We also deduce a hitting time result for the random hypergraph process -- the hypergraph becomes $j$-connected at exactly the moment when the last isolated $j$-set disappears. This generalises well-known results for graphs.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.