Name
Abstract | ||
|---|---|---|
Let 3 ≤ k n/2. We prove the analogue of the Erdős–Ko–Rado theorem for the random k-uniform hypergraph Gk(n, p) when k n/2)1/3; that is, we show that with probability tending to 1 as n → ∞, the maximum size of an intersecting subfamily of Gk(n, p) is the size of a maximum trivial family. The analogue of the Erdős–Ko–Rado theorem does not hold for all p when k ≫ n1/3. We give quite precise results for k n1/2−ϵ. For larger k we show that the random Erdős–Ko–Rado theorem holds as long as p is not too small, and fails to hold for a wide range of smaller values of p. Along the way, we prove that every non-trivial intersecting k-uniform hypergraph can be covered by k2 − k + 1 pairs, which is sharp as evidenced by projective planes. This improves upon a result of Sanders [7]. Several open questions remain. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1017/S0963548309990253 | Combinatorics, Probability & Computing |
Keywords | Field | DocType |
intersecting subfamily,rado theorem,random k-uniform hypergraph,k n,random erd,larger k,k n1,maximum size,maximum trivial family,k-uniform hypergraph,random hypergraphs,projective plane | Discrete mathematics,Combinatorics,Constraint graph,Hypergraph,Projective plane,Mathematics | Journal |
Volume | Issue | ISSN |
18 | 5 | 0963-5483 |
Citations | PageRank | References |
5 | 0.67 | 4 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| József Balogh | 1 | 862 | 89.91 |
| Tom Bohman | 2 | 250 | 33.01 |
| Dhruv Mubayi | 3 | 579 | 73.95 |