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.
ASJC Scopus subject areas
- Discrete Mathematics and Combinatorics
Treatment code (Nähere Zuordnung)
- Basic - Fundamental (Grundlagenforschung)