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

preprint2016arXivOpen access

Abstract

The celebrated Erdős-Ko-Rado theorem determines the maximum size of a kk-uniform intersecting family. The Hilton-Milner theorem determines the maximum size of a kk-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 kk-uniform family that is neither a subfamily of the Erdős-Ko-Rado family nor of the Hilton-Milner family is. For k≥4k\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≥3k\ge 3 and characterize all extremal families achieving the extremal value.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.