On the Erdős-Ko-Rado theorem and the Bollobás theorem for t-intersecting families
On the Erdős-Ko-Rado theorem and the Bollobás theorem for t-intersecting families
复制标题
关于 t 相交族的 Erdős-Ko-Rado 定理和 Bollobás 定理
DOI：
10.1016/j.ejc.2015.01.009
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Younjin Kim
中科院分区：
文献类型：
--
作者：
D. Kang;Jaehoon Kim;Younjin Kim
一个族F是t-相交的，如果任何两个成员至少有t个公共元素。Erdans，Ko和Rado（1961）证明了一个由大小为k的子集组成的t-交族的最大大小等于n-tk-t，如果n≥ n 0（k，t）。Alon，Aydinian and Huang（2014）考虑了族对相交族的推广，并证明了相同的界。本文通过考虑族对所有t≥ 1推广t-交族，加强了他们的结果。2004年，塔尔博特将Bollobás的两族定理（Bollobás，1965）推广到t-相交族。本文用概率方法证明了塔尔博特结果的一个小推广。
A family F is t-intersecting if any two members have at least t common elements. Erdős, Ko and Rado (1961) proved that the maximum size of a t-intersecting family of subsets of size k is equal to n− t k− t if n≥ n 0 (k, t). Alon, Aydinian and Huang (2014) considered families generalizing intersecting families, and proved the same bound. In this paper, we give a strengthening of their result by considering families generalizing t-intersecting families for all t≥ 1. In 2004, Talbot generalized Bollobás’s Two Families Theorem (Bollobás, 1965) to t-intersecting families. In this paper, we proved a slight generalization of Talbot’s result by using the probabilistic method.