Erdos-Ko-Rado for Random Hypergraphs: Asymptotics and Stability
Result description
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.
Keywords
The result's identifiers
Result code in IS VaVaI
Result on the web
DOI - Digital Object Identifier
Alternative languages
Result language
angličtina
Original language name
Erdos-Ko-Rado for Random Hypergraphs: Asymptotics and Stability
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
Jimp - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10101 - Pure mathematics
Result continuities
Project
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2017
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Combinatorics, Probability & Computing
ISSN
0963-5483
e-ISSN
—
Volume of the periodical
26
Issue of the periodical within the volume
3
Country of publishing house
GB - UNITED KINGDOM
Number of pages
17
Pages from-to
406-422
UT code for WoS article
000398967400004
EID of the result in the Scopus database
—
Basic information
Result type
Jimp - Article in a specialist periodical, which is included in the Web of Science database
OECD FORD
Pure mathematics
Year of implementation
2017