Erdős-Ko-Rado for random hypergraphs: asymptotics and stability

Abstract

We investigate the asymptotic version of the Erdős-Ko-Rado theorem for the random $k$-uniform hypergraph ${\mathcal{H}}^k(n,p)$. For $2\le k(n)\le n/2$, let $N=\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ and $D=\left(\genfrac{}{}{0ex}{}{n-k}{k}\right)$. We show that with probability tending to 1 as $n\to \infty$, the largest intersecting subhypergraph of ${\mathcal{H}}^k(n,p)$ has size $(1+o(1))p\frac{k}{n}N$, for any $p\gg \frac{n}{k}{\ln }^2\left(\frac{n}{k}\right)D^{-1}$. This lower bound on $p$ is asymptotically best possible for $k=\Theta (n)$. For this range of $k$ and $p$, we are able to show stability as well. A different behavior occurs when $k=o(n)$. In this case, the lower bound on $p$ is almost optimal. Further, for the small interval $D^{-1}\ll p\le (n/k{)}^{1-\epsilon }{D}^{-1}$, the largest intersecting subhypergraph of ${\mathcal{H}}^k(n,p)$ has size $\Theta (\ln (pD)N{D}^{-1})$, provided that $k\gg \sqrt{n\ln n}$. Together with previous work of Balogh, Bohman and Mubayi, these results settle the asymptotic size of the largest intersecting family in ${\mathcal{H}}^k(n,p)$, for essentially all values of $p$ and $k$.