Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

Request Permissions   Purchase Content 
 

 

The maximum size of a non-trivial intersecting uniform family that is not a subfamily of the Hilton-Milner family


Authors: Jie Han and Yoshiharu Kohayakawa
Journal: Proc. Amer. Math. Soc. 145 (2017), 73-87
MSC (2010): Primary 05D05
DOI: https://doi.org/10.1090/proc/13221
Published electronically: June 30, 2016
MathSciNet review: 3565361
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2010): 05D05

Retrieve articles in all journals with MSC (2010): 05D05


Additional Information

Jie Han
Affiliation: Instituto de Matemática e Estatística, Universidade de São Paulo, Rua do Matão 1010, 05508-090, São Paulo, Brazil
Email: jhan@ime.usp.br

Yoshiharu Kohayakawa
Affiliation: Instituto de Matemática e Estatística, Universidade de São Paulo, Rua do Matão 1010, 05508-090, São Paulo, Brazil
Email: yoshi@ime.usp.br

DOI: https://doi.org/10.1090/proc/13221
Keywords: Intersecting families, Hilton--Milner theorem, Erd\H{o}s--Ko--Rado theorem
Received by editor(s): September 17, 2015
Received by editor(s) in revised form: February 6, 2016, and March 22, 2016
Published electronically: June 30, 2016
Additional Notes: The first author was supported by FAPESP (2014/18641-5, 2015/07869-8)
The second author was partially supported by FAPESP (2013/03447-6, 2013/07699-0), CNPq (459335/2014-6, 310974/2013-5 and 477203/2012-4) and the NSF (DMS 1102086)
The authors acknowledge the support of NUMEC/USP (Project MaCLinC/USP)
Communicated by: Patricia L. Hersh
Article copyright: © Copyright 2016 American Mathematical Society