The minimum number of disjoint pairs in set systems and related problems
The minimum number of disjoint pairs in set systems and related problems
复制标题
集合系统中不相交对的最小数量及相关问题
DOI：
10.1007/s00493-014-3133-0
复制
发表时间：
2013
期刊：
影响因子：
1.1
通讯作者：
B. Sudakov
中科院分区：
文献类型：
--
作者：
Shagnik Das;Wenying Gan;B. Sudakov
设F是[n]上的一个集合系统，所有集合有k个元素，且每对集合相交。1961年Erdés、Ko和Rado的著名定理说，只要n ≥ 2k，任何这样的系统最多有大小。一个自然的问题，这是问Ahlswede在1980年，是有多少不相交对必须出现在一套系统的规模较大。除了Ahlswede和Katona解决了k = 2的情形外，这个问题在过去的30年里一直没有得到解决.本文确定了小k-一致族中不相交对的最小数目，从而证实了Bollobás和Leader在这些情形下的一个猜想.此外，我们获得了类似的结果，两个著名的扩展的Erdens-Ko-Rado定理，确定最小数量的匹配的大小q和最小数量的t-不相交的对出现在集系统大于相应的极值界限。在后一种情况下，这为Kleitman和West的问题提供了部分解决方案。
LetFbe a set system on [n] with all sets havingkelements and every pair of sets intersecting. The celebrated theorem of Erdős, Ko and Rado from 1961 says that, providedn≥ 2k, any such system has size at most. A natural question, which was asked by Ahlswede in 1980, is how many disjoint pairs must appear in a set system of larger size. Except for the casek= 2, solved by Ahlswede and Katona, this problem has remained open for the last three decades.In this paper, we determine the minimum number of disjoint pairs in smallk-uniform families, thus confirming a conjecture of Bollobás and Leader in these cases. Moreover, we obtain similar results for two well-known extensions of the Erdős-Ko-Rado Theorem, determining the minimum number of matchings of sizeqand the minimum number oft-disjoint pairs that appear in set systems larger than the corresponding extremal bounds. In the latter case, this provides a partial solution to a problem of Kleitman and West.