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

Autor(es)

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

• Tipo de documento: Artigo Científico
• Fonte: COMBINATORICS PROBABILITY & COMPUTING; v. 26, n. 3, p. 406-422, MAY 2017.
• Citações Web of Science: 0

Resumo

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)

• Processo FAPESP: 13/11353-1 - Problemas extremais degenerados para estruturas aleatórias discretas
• Beneficiário: Hiep Han
• Modalidade de apoio: Bolsas no Exterior - Estágio de Pesquisa - Pós-Doutorado
• Processo FAPESP: 10/16526-3 - Hipergrafos quase-aleatórios e imersão de subhipergrafos geradores
• Beneficiário: Hiep Han
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado