Erdős–Ko–Rado in Random Hypergraphs
Erdős–Ko–Rado in Random Hypergraphs
复制标题
随机超图中的 Erdős–Ko–Rado
DOI：
10.1017/s0963548309990253
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
D. Mubayi
中科院分区：
文献类型：
--
作者：
J. Balogh;T. Bohman;D. Mubayi
设3 ≤ k < n/2。当k <（n/2）1/3时，我们证明了随机k-一致超图Gk（n，p）的Erdens-Ko-Rado定理的类似定理，即当n → ∞时概率趋于1时，Gk（n，p）的相交子族的最大规模是极大平凡族的规模.当k = 1/3时，Erdens-Ko-Rado定理的类似物并不对所有p都成立。对于k < n1/2− n，我们给出了相当精确的结果。对于较大的k，我们证明了随机Erdens-Ko-Rado定理只要p不太小就成立，而对于p的更小值则不成立。沿着这条路，我们证明了每个非平凡相交的k-一致超图都可以被k2 − k + 1对覆盖，这一点通过投影平面得到了证明。这改进了Sanders的结果[7]。还有几个悬而未决的问题。
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.