Intersecting families of discrete structures are typically trivial
Intersecting families of discrete structures are typically trivial
复制标题
离散结构的相交族通常是微不足道的
DOI：
10.1016/j.jcta.2015.01.003
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
M. Sharifzadeh
中科院分区：
文献类型：
--
作者：
J. Balogh;Shagnik Das;Michelle Delcourt;Hong Liu;M. Sharifzadeh
相交结构的研究是极值组合学的核心。一个排列族F⊂S n是t交的，如果F中的任意两个排列在某些t指数上一致，并且如果F中的所有排列都在相同的t指数上一致，则F是平凡的。如果k-一致超图的任意两条边都有t个公共顶点，则它是t-交的；如果k-一致超图的所有边都共享相同的t个顶点，则它是平凡的。基本问题是确定相交族可以有多大。Ellis，Friedgut和Pilpel证明了对于关于t足够大的n，S n中最大的t-交族是平凡的。经典的ERDőS-Ko-Rado定理表明，当n较大时，最大t-交k-一致超图也是平凡的。我们确定了t-交族的典型结构，推广了这些结果，表明几乎所有的交族都是平凡的。我们还得到了这些极值结果的稀疏类似结果，表明它们在随机设置下成立。我们的证明使用BollobáS集对不等式来确定极大交族的个数，然后结合已知的稳定性定理。对于向量空间，我们也得到了类似的结果。
The study of intersecting structures is central to extremal combinatorics. A family of permutations F⊂ S n is t-intersecting if any two permutations in F agree on some t indices, and is trivial if all permutations in F agree on the same t indices. A k-uniform hypergraph is t-intersecting if any two of its edges have t vertices in common, and trivial if all its edges share the same t vertices. The fundamental problem is to determine how large an intersecting family can be. Ellis, Friedgut and Pilpel proved that for n sufficiently large with respect to t, the largest t-intersecting families in S n are the trivial ones. The classic Erdős–Ko–Rado theorem shows that the largest t-intersecting k-uniform hypergraphs are also trivial when n is large. We determine the typical structure of t-intersecting families, extending these results to show that almost all intersecting families are trivial. We also obtain sparse analogues of these extremal results, showing that they hold in random settings. Our proofs use the Bollobás set-pairs inequality to bound the number of maximal intersecting families, which can then be combined with known stability theorems. We also obtain similar results for vector spaces.