The maximum size of a non-trivial intersecting uniform family that is not a subfamily of the Hilton-Milner family
Sep 26, 2017
Jie Han and Yoshiharu Kohayakawa
The celebrated Erdos–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 Erdos–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 Erdos–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.
The whole paper is available here.
Share on Facebook
