Journal
PROCEEDINGS OF THE AMERICAN MATHEMATICAL SOCIETY
Volume 145, Issue 1, Pages 73-87Publisher
AMER MATHEMATICAL SOC
DOI: 10.1090/proc/13221
Keywords
Intersecting families; Hilton-Milner theorem; Erdos-Ko-Rado theorem
Categories
Funding
- FAPESP [2014/18641-5, 2015/07869-8, 2013/03447-6, 2013/07699-0]
- CNPq [459335/2014-6, 310974/2013-5, 477203/2012-4]
- NSF [DMS 1102086]
- NUMEC/USP (MaCLinC/USP)
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available