Erdős–Ko–Rado for Random Hypergraphs: Asymptotics and Stability. (29th March 2017)

• Record Type: Journal Article
• Authors: GAUY, MARCELO M.; HÀN, HIÊP; OLIVEIRA, IGOR C.
• Is Part Of: Combinatorics, probability and computing. Volume 26:Number 3(2017:May)
• Page Start: 406
• Page End: 422
• Publication Date: 2017-03-29
• Subjects: Primary 05D05, -- Secondary 05D40; Combinatorial analysis -- Periodicals; Probabilities -- Periodicals; Computer science -- Mathematics -- Periodicals; 511.6
• DOI: 10.1017/S0963548316000420
• Languages: English
• ISSNs: 0963-5483

Abstract

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⩽ k ( n ) ⩽ n /2, let $N=\binom{n}k$ and $D=\binom{n-k}k$ . We show that with probability tending to 1 as n → ∞, the largest intersecting subhypergraph of $\mathcal{H}$ has size $$(1+o(1))p\ffrac kn N$$ for any $$p\gg \ffrac nk\ln^2\biggl(\ffrac nk\biggr)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 $\mathcal{H}$ k ( n, p ) has size Θ(ln( pD ) ND −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, for essentially all values of p and k .