pith. sign in

arxiv: 1509.05464 · v4 · pith:D24I7WF7new · submitted 2015-09-17 · 🧮 math.CO

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

classification 🧮 math.CO
keywords familyintersectingmaximumsizeuniformhilton-milners-ko-radosubfamily
0
0 comments X
read the original abstract

The celebrated Erd\H{o}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\H{o}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\H{o}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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.