Beyond the Erdös-Ko-Rado theorem
Beyond the Erdös-Ko-Rado theorem
复制标题
超越鄂尔多斯-科-拉多定理
DOI：
10.1016/0097-3165(91)90031-b
复制
发表时间：
1991
期刊：
影响因子：
--
通讯作者：
Z. Füredi
中科院分区：
文献类型：
--
作者：
P. Frankl;Z. Füredi
Erdős-Ko-Rado定理的确切界是已知的[F， W]。它指出，如果n≠(t+ 1)(k−t+ 1)，并且F是一个n集的k集的t相交族（| F∩F ' |≠t对于所有F， F '∈F），则| F≤(n−1 k−1)。定义一个r = {F⊂{1,2,…,n}: F | | = k, | F∩{1,2,…,t + 2 r} |⩾t + r}。这里证明了对于n> c t log (t+ 1)（k−t+ 1）有| F|≤max r| A r|。
The exact bound in the Erdős-Ko-Rado theorem is known [F, W]. It states that if n⩾(t+ 1)(k− t+ 1), and F is a t-intersecting family of k-sets of an n-set (| F∩ F′|⩾ t for all F, F′∈ F), then| F⩽(n− 1 k− 1). Define A r={F⊂{1, 2,…, n}:| F|= k,| F∩{1, 2,…, t+ 2r}|⩾ t+ r}. Here it is proved that for n> c t log (t+ 1)(k− t+ 1) one has| F|⩽ max r| A r|.