The maximum number of disjoint pairs in a family of subsets
The maximum number of disjoint pairs in a family of subsets
复制标题
子集族中不相交对的最大数量
DOI：
--
复制
发表时间：
1985
期刊：
影响因子：
--
通讯作者：
P. Frankl
中科院分区：
文献类型：
--
作者：
N. Alon;P. Frankl
设一个2n元素集合的2n+1个子集的族。则不相交对的个数以（1+o(1)）22n为界。这证明了Erdös的一个老猜想。设<s:1>元集的21/(k+1)+δ)n个子集的族。那么，在这个序列中，包含的个数以（1-1/k+o(1)）（2| |）为界。这证实了Daykin和Erdös的一个猜想。对于子集族中不相交对的最大数目，证明了一个类似的Erdös-Stone型结果。
Let ℱ be a family of 2n+1 subsets of a 2n-element set. Then the number of disjoint pairs in ℱ is bounded by (1+o(1))22n. This proves an old conjecture of Erdös. Let ℱ be a family of 21/(k+1)+δ)n subsets of ann-element set. Then the number of containments in ℱ is bounded by (1-1/k+o(1))(2|ℱ|). This verifies a conjecture of Daykin and Erdös. A similar Erdös-Stone type result is proved for the maximum number of disjoint pairs in a family of subsets.