The size of the giant high‐order component in random hypergraphs. Issue 2 (5th February 2018)

• Record Type: Journal Article
• Authors: Cooley, Oliver; Kang, Mihyun; Koch, Christoph
• Is Part Of: Random structures & algorithms. Volume 53:Issue 2(2018)
• Page Start: 238
• Page End: 288
• Publication Date: 2018-02-05
• Subjects: branching process -- degree -- giant component -- high‐order connectedness -- phase transition -- random hypergraphs; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20761
• Languages: English
• ISSNs: 1042-9832

Abstract

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 .