Largest Components in Random Hypergraphs. (4th April 2018)

• Record Type: Journal Article
• Authors: COOLEY, OLIVER; KANG, MIHYUN; PERSON, YURY
• Is Part Of: Combinatorics, probability and computing. Volume 27:Number 5(2018)
• Page Start: 741
• Page End: 762
• Publication Date: 2018-04-04
• Subjects: Primary 05C65, -- Secondary 05C80; Combinatorial analysis -- Periodicals; Probabilities -- Periodicals; Computer science -- Mathematics -- Periodicals; 511.6
• DOI: 10.1017/S096354831800010X
• Languages: English
• ISSNs: 0963-5483

Abstract

Abstract : In this paper we consider j -tuple-connected components in random k -uniform hypergraphs (the j -tuple-connectedness relation can be defined by letting two j -sets be connected if they lie in a common edge and considering the transitive closure; the case j = 1 corresponds to the common notion of vertex-connectedness). We show that the existence of a j -tuple-connected component containing Θ( n j ) j -sets undergoes a phase transition and show that the threshold occurs at edge probability $$\frac{(k-j)!}{\binom{k}{j}-1}n^{j-k}.$$ Our proof extends the recent short proof for the graph case by Krivelevich and Sudakov, which makes use of a depth-first search to reveal the edges of a random graph. Our main original contribution is a bounded degree lemma, which controls the structure of the component grown in the search process.