A degree version of the Hilton-Milner theorem

作者：Frankl Peter^*; Han Jie; Huang Hao; Zhao Yi

来源：Journal of Combinatorial Theory - Series A, 2018, 155: 493-502.

DOI：10.1016/j.jcta.2017.11.019

• Intersecting families
• Hilton-Milner theorem
• Erdds-Ko-Rado theorem

An intersecting family of sets is trivial if all of its members share a common element. Hilton and Milner proved a strong stability result for the celebrated Erdos-Ko-Rado theorem: when n > 2k, every non-trivial intersecting family of k-subsets of [n] has at most (n-1k-1) - (n-k-1 k-1) +1 members. One extremal family HMn,k consists of a k-set S and all k-subsets of [n] containing a fixed element x is an element of S and at least one element of S. We prove a degree version of the Hilton-Milner theorem: if n = Omega(k(2)) and F is a non-trivial intersecting family of k-subsets of [n], then delta(F) <= (HMn,k), where delta(F) denotes the minimum (vertex) degree of F. Our proof uses several fundamental results in extremal set theory, the concept of kernels, and a new variant of the Erdos-Ko-Rado theorem.

• 出版日期2018-4