Erdős–Ko–Rado for Random Hypergraphs: Asymptotics and Stability. (29th March 2017) - GAUY, MARCELO M.; HÀN, HIÊP; OLIVEIRA, IGOR C.
Abstract : We investigate the asymptotic version of the Erdős–Ko–Rado theorem for the random k -uniform hypergraph H k ( n, p ). For 2⩽ k ( n ) ⩽ n /2, let N=nk and D=n-kk . We show that with probability tending to 1 as n → ∞, the largest intersecting subhypergraph of H has size (1+o(1))pkn N for any pnk^2(nk)D^-1. This lower bound on p is asymptotically best possible for k = Θ( n ). For this range of k and p, we are able to show stability as well. A different behaviour occurs when k = o ( n ). In this case, the lower bound on p is almost optimal. Further, for the small interval D −1 ≪ p ⩽ ( n / k ) 1−ϵ D −1, the largest intersecting subhypergraph of H k ( n, p ) has size Θ(ln( pD ) ND −1 ), provided that k n n . Together with previous work of Balogh, Bohman and Mubayi, these results settle the asymptotic size of the largest intersecting family in H k, for essentially all values of p and k .