The size of the giant high‐order component in random hypergraphs. Issue 2 (5th February 2018) - Cooley, Oliver; Kang, Mihyun; Koch, Christoph
Abstract: The phase transition in the size of the giant component in random graphs is one of the most well‐studied phenomena in random graph theory. For hypergraphs, there are many possible generalizations of the notion of a connected component. We consider the following: 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. A hypergraph is j ‐connected if all j ‐sets are pairwise j ‐connected. In this paper, we determine the asymptotic size of the unique giant j ‐connected component in random k ‐uniform hypergraphs for any k ≥ 3 and 1 ≤ j ≤ k − 1 .