Threshold and hitting time for high-order connectedness in random hypergraphs (Q2629490): Difference between revisions

Summary: 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 \textit{B. Bollobás} and \textit{A. Thomason} [ Ann. Discrete Math. 28, 47--97 (1985; Zbl 0588.05040)] for graphs.