Erd\H{o}s-Ko-Rado for random hypergraphs: asymptotics and stability

Abstract

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