TY - JOUR
T1 - A degree version of the Hilton–Milner theorem
AU - Frankl, Peter
AU - Han, Jie
AU - Huang, Hao
AU - Zhao, Yi
N1 - Publisher Copyright:
© 2017 Elsevier Inc.
PY - 2018/4
Y1 - 2018/4
N2 - 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 Erdős–Ko–Rado theorem: when n>2k, every non-trivial intersecting family of k-subsets of [n] has at most (n−1k−1)−(n−k−1k−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∉S and at least one element of S. We prove a degree version of the Hilton–Milner theorem: if n=Ω(k2) and F is a non-trivial intersecting family of k-subsets of [n], then δ(F)≤δ(HMn.k), where δ(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 Erdős–Ko–Rado theorem.
AB - 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 Erdős–Ko–Rado theorem: when n>2k, every non-trivial intersecting family of k-subsets of [n] has at most (n−1k−1)−(n−k−1k−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∉S and at least one element of S. We prove a degree version of the Hilton–Milner theorem: if n=Ω(k2) and F is a non-trivial intersecting family of k-subsets of [n], then δ(F)≤δ(HMn.k), where δ(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 Erdős–Ko–Rado theorem.
KW - Erdős–Ko–Rado theorem
KW - Hilton–Milner theorem
KW - Intersecting families
UR - http://www.scopus.com/inward/record.url?scp=85040767038&partnerID=8YFLogxK
U2 - 10.1016/j.jcta.2017.11.019
DO - 10.1016/j.jcta.2017.11.019
M3 - Article
AN - SCOPUS:85040767038
SN - 0097-3165
VL - 155
SP - 493
EP - 502
JO - Journal of Combinatorial Theory. Series A
JF - Journal of Combinatorial Theory. Series A
ER -