Birth and growth of multicyclic components in random hypergraphs

Define an ℓ-component to be a connected b-uniform hypergraph with k edges and k(b−1)−ℓ vertices. In this paper, we investigate the growth of size and complexity of connected components of a random hypergraph process. We prove that the expected number of creations of ℓ-components during a random hypergraph process tends to 1 as b is fixed and ℓ tends to infinity with the total number of vertices n while remaining ℓ=o(n1/3). We also show that the expected number of vertices that ever belong to an ℓ-component is ∼121/3ℓ1/3n2/3(b−1)−1/3. We prove that the expected number of times hypertrees are swallowed by ℓ-components is ∼21/33−1/3n1/3ℓ−1/3(b−1)−5/3. It follows that with high probability the largest ℓ-component during the process is of size of order O(ℓ1/3n2/3(b−1)−1/3). Our results give insight into the size of giant components inside the phase transition of random hypergraphs and generalize previous results about graphs.