05697157

j

05697157 Balogh, J\'ozsef Bohman, Tom Mubayi, Dhruv Erd\H os-Ko-Rado in random hypergraphs. Comb. Probab. Comput. 18, No. 5, 629-646 (2009). 2009 Cambridge University Press, Cambridge EN Erdoes-Ko-Rado theorem random uniform hypergraph Zbl 1064.05143

doi:10.1017/S0963548309990253

Summary: Let $3 \leqslant k < n/2$. We prove the analogue of the Erd\H os-Ko-Rado theorem for the random $k$-uniform hypergraph $G^{k}(n, p)$ when $k < (n/2)^{1/3}$; that is, we show that with probability tending to 1 as $n \rightarrow \infty $, the maximum size of an intersecting subfamily of $G^{k}(n, p)$ is the size of a maximum trivial family. The analogue of the Erd\H os-Ko-Rado theorem does not hold for all $p$ when $k\gg n^{1/3}$. We give quite precise results for $k < n^{1/2-\varepsilon}$. For larger $k$ we show that the random Erd\H os-Ko-Rado theorem holds as long as $p$ is not too small, and fails to hold for a wide range of smaller values of $p$. Along the way, we prove that every non-trivial intersecting $k$-uniform hypergraph can be covered by $k^2- k + 1$ pairs, which is sharp as evidenced by projective planes. This improves upon a result of Sanders [{\it A.J. Sanders}, ``Covering by intersecting families'', J. Comb. Theory, Ser. A 108, No.\,1, 51--61 (2004; Zbl 1064.05143)]. Several open questions remain.