TY - JOUR
T1 - The maximum size of a non-trivial intersecting uniform family that is not a subfamily of the Hilton–Milner family
AU - Han, Jie
AU - Kohayakawa, Yoshiharu
N1 - Publisher Copyright:
© 2016 American Mathematical Society.
PY - 2017
Y1 - 2017
N2 - The celebrated Erdős–Ko–Rado theorem determines the maximum size of a k-uniform intersecting family. The Hilton–Milner theorem determines the maximum size of a k-uniform intersecting family that is not a subfamily of the so-called Erdős–Ko–Rado family. In turn, it is natural to ask what the maximum size of an intersecting k-uniform family that is neither a subfamily of the Erdős–Ko–Rado family nor of the Hilton–Milner family is. For k ≥ 4, this was solved (implicitly) in the same paper by Hilton–Milner in 1967. We give a different and simpler proof, based on the shifting method, which allows us to solve all cases k ≥ 3 and characterize all extremal families achieving the extremal value.
AB - The celebrated Erdős–Ko–Rado theorem determines the maximum size of a k-uniform intersecting family. The Hilton–Milner theorem determines the maximum size of a k-uniform intersecting family that is not a subfamily of the so-called Erdős–Ko–Rado family. In turn, it is natural to ask what the maximum size of an intersecting k-uniform family that is neither a subfamily of the Erdős–Ko–Rado family nor of the Hilton–Milner family is. For k ≥ 4, this was solved (implicitly) in the same paper by Hilton–Milner in 1967. We give a different and simpler proof, based on the shifting method, which allows us to solve all cases k ≥ 3 and characterize all extremal families achieving the extremal value.
KW - Erdős-Ko-Rado theorem
KW - Hilton-Milner theorem
KW - Intersecting families
UR - http://www.scopus.com/inward/record.url?scp=84994275803&partnerID=8YFLogxK
U2 - 10.1090/proc/13221
DO - 10.1090/proc/13221
M3 - Article
AN - SCOPUS:84994275803
SN - 0002-9939
VL - 145
SP - 73
EP - 87
JO - Proceedings of the American Mathematical Society
JF - Proceedings of the American Mathematical Society
IS - 1
ER -