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

Jie Han, Yoshiharu Kohayakawa

Research output: Contribution to journalArticlepeer-review

26 Citations (Scopus)

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 ≥ 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.

Original languageEnglish
Pages (from-to)73-87
Number of pages15
JournalProceedings of the American Mathematical Society
Volume145
Issue number1
DOIs
Publication statusPublished - 2017
Externally publishedYes

Keywords

  • Erdős-Ko-Rado theorem
  • Hilton-Milner theorem
  • Intersecting families

Fingerprint

Dive into the research topics of 'The maximum size of a non-trivial intersecting uniform family that is not a subfamily of the Hilton–Milner family'. Together they form a unique fingerprint.

Cite this