The maximum size of a non-trivial intersecting uniform family that is not a subfamily of the Hilton–Milner family
Open Access
- 30 June 2016
- journal article
- research article
- Published by American Mathematical Society (AMS) in Proceedings of the American Mathematical Society
- Vol. 145 (1) , 73-87
Abstract
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\ge 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\ge 3$ and characterize all extremal families achieving the extremal value.
Keywords
All Related Versions
Funding Information
- Fundação de Amparo à Pesquisa do Estado de São Paulo (2014/18641-5, 2015/07869-8, 2013/03447-6, 2013/07699-0, 310974/2013-5, 459335/2014-6, 477203/2012-4, DMS 1102086)