Premium
The size of the giant high‐order component in random hypergraphs
Author(s) -
Cooley Oliver,
Kang Mihyun,
Koch Christoph
Publication year - 2018
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20761
Subject(s) - giant component , connected component , combinatorics , mathematics , hypergraph , random graph , component (thermodynamics) , pairwise comparison , discrete mathematics , order (exchange) , graph , statistics , physics , finance , economics , thermodynamics
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 .