New Results on Simplex-Clusters in Set Systems
New Results on Simplex-Clusters in Set Systems
复制标题
集合系统中单纯形簇的新结果
作者：
Gabriel Currier
d-单纯形被定义为集合A1，.，Ad+1是[n]的大小为k的子集的集合，使得所有子集的交集都是空的，但其中任何d个子集的交集都是非空的。此外，d-簇是d+1个这样的集合的集合，其交集和并集的大小≤ 2k，而d-单纯形簇是这样的集合，它既是d-单纯形又是d-簇。1974年的Erdös-Chvátal d-单形猜想指出，任何不含d-单形的[n]的k-子集族的大小必须不大于（n-1/n-1）。在2011年，Keevash和Mubayi扩展了这个猜想，假设同样的界限也适用于不包含d-单形簇的族。在本文中，我们解决了Keevash和Mubayi的猜想，对于所有4 ≤ d + 1 ≤ k和n ≥ 2k-d + 2，这反过来解决了Erdös-Chvatal猜想的所有剩余情况，除了当n很小时（即n < 2k-d + 2）。
A d-simplex is defined to be a collection A1,..., Ad+1 of subsets of size k of [n] such that the intersection of all of them is empty, but the intersection of any d of them is non-empty. Furthemore, a d-cluster is a collection of d+1 such sets with empty intersection and union of size ≤ 2k, and a d-simplex-cluster is such a collection that is both a d-simplex and a d-cluster. The Erdös-Chvátal d-simplex Conjecture from 1974 states that any family of k-subsets of [n] containing no d-simplex must be of size no greater than (n-1/n-1). In 2011, Keevash and Mubayi extended this conjecture by hypothesizing that the same bound would hold for families containing no d-simplex-cluster. In this paper, we resolve Keevash and Mubayi’s conjecture for all 4 ≤ d + 1 ≤ k and n ≥ 2k - d + 2, which in turn resolves all remaining cases of the Erdös-Chvatal Conjecture except when n is very small (i.e. n < 2k-d + 2).