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

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.

 

NeuroMat

The Research, Innovation and Dissemination Center for Neuromathematics is hosted by the University of São Paulo and funded by FAPESP (São Paulo Research Foundation).

 

User login

 

Contact

Address:
1010 Matão Street - Cidade Universitária - São Paulo - SP - Brasil. 05508-090. See map.

Phone:
55 11 3091-1717

General contact email:
neuromat@numec.prp.usp.br

Media inquiries email:
comunicacao@numec.prp.usp.br