Threshold and Hitting Time for High-Order Connectedness in Random Hypergraphs

  • Oliver Cooley Graz University of Technology
  • Mihyun Kang Graz University of Technology
  • Christoph Koch Graz University of Technology
Keywords: Random Hypergraphs, Connectivity, Hitting Time

Abstract

We consider the following definition of connectedness in $k$-uniform hypergraphs: two $j$-sets (sets of $j$ vertices) are $j$-connected if there is a walk of edges between them such that two consecutive edges intersect in at least $j$ vertices. The hypergraph is $j$-connected if all $j$-sets are pairwise $j$-connected. 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 the classical hitting time result of Bollobás and Thomason for graphs.

Published
2016-06-10
Article Number
P2.48