The size of the giant high‐order component in random hypergraphs
- 5 February 2018
- journal article
- research article
- Published by Wiley in Random Structures & Algorithms
- Vol. 53 (2) , 238-288
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 and .Keywords
All Related Versions
Funding Information
- Austrian Science Fund (P26826, W1230)
This publication has 15 references indexed in Scilit:
- The phase transition in random graphs: A simple proofRandom Structures & Algorithms, 2012
- Asymptotic normality of the size of the giant component in a random hypergraphRandom Structures & Algorithms, 2012
- The phase transition in the cluster‐scaled model of a random graphRandom Structures & Algorithms, 2005
- Cores in random hypergraphs and Boolean formulasRandom Structures & Algorithms, 2005
- Counting connected graphs inside-outJournal of Combinatorial Theory, Series B, 2005
- The phase transition in a random hypergraphJournal of Computational and Applied Mathematics, 2002
- Sudden Emergence of a Giantk-Core in a Random GraphJournal of Combinatorial Theory, Series B, 1996
- The birth of the giant componentRandom Structures & Algorithms, 1993
- Component structure in the evolution of random hypergraphsCombinatorica, 1985
- The Evolution of Random GraphsTransactions of the American Mathematical Society, 1984