Creation and Growth of Components in a Random Hypergraph Process

Abstract

Denote by an $\ell$-component a connected $b$-uniform hypergraph with $k$ edges and $k(b-1)-\ell$ vertices. We prove that the expected number of creations of $\ell$-component during a random hypergraph process tends to 1 as $\ell$ and $b$ tend to $\infty$ with the total number of vertices $n$ such that $\ell =o(\sqrt[3]{\frac{n}{b}})$. Under the same conditions, we also show that the expected number of vertices that ever belong to an $\ell$-component is approximately $12^{1/3}(b-1{)}^{1/3}{\ell }^{1/3}{n}^{2/3}$. As an immediate consequence, it follows that with high probability the largest $\ell$-component during the process is of size $O((b-1{)}^{1/3}{\ell }^{1/3}{n}^{2/3})$. Our results give insight about the size of giant components inside the phase transition of random hypergraphs.

Résumé étendu