Erdos-Ko-Rado for Random Hypergraphs: Asymptotics and Stability

Author(s)

Gauy, Marcelo M. ; Han, Hiep ; Oliveira, Igor C.

• Document type: Journal article
• Source: COMBINATORICS PROBABILITY & COMPUTING; v. 26, n. 3, p. 406-422, MAY 2017.
• Web of Science Citations: 0

Abstract

We investigate the asymptotic version of the Erdos-Ko-Rado theorem for the random k-uniform hypergraph H-k(n, p). For 2 <= k(n) <= n/2, let N = (n/k) and D = (n-k/k). We show that with probability tending to 1 as n -> infinity, the largest intersecting subhypergraph of Hk( n, p) has size (1+o(1))p(n)(k)-N for any p >> n/k ln(2) (n/k) 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 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(-epsilon)D(-1), the largest intersecting subhypergraph of Hk(n, p) has size Theta(ln(pD) ND-1), provided that k >> root nlnn. Together with previous work of Balogh, Bohman and Mubayi, these results settle the asymptotic size of the largest intersecting family in H-k(n, p), for essentially all values of p and k. (AU)

• FAPESP's process: 13/11353-1 - Degenerate extremal problems for random discrete structures
• Grantee: Hiep Han
• Support Opportunities: Scholarships abroad - Research Internship - Post-doctor
• FAPESP's process: 10/16526-3 - Quasi-random hypergraphs and spanning subhypergraph containment
• Grantee: Hiep Han
• Support Opportunities: Scholarships in Brazil - Post-Doctoral