Largest Components in Random Hypergraphs

Source 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.