A simple proof of the Hilton-Milner theorem. (English) Zbl 1414.05289

Frankl, Peter

Mosc. J. Comb. Number Theory 8, No. 2, 97-101 (2019).

Summary: Let \(n \geq 2k \geq 4\) be integers and \(\mathcal{F}\) a family of \(k\)-subsets of \(\{1,2,\dots, n\}\). We call \(\mathcal{F}\) intersecting if \(F \cap F' \neq \emptyset\) for all \(F, F' \in \mathcal{F}\), and we call \(\mathcal{F}\) nontrivial if \(\bigcap_{F \in \mathcal{F}} F = \emptyset\). Strengthening the famous Erdős-Ko-Rado theorem, A. Hilton and E. Milner [Q. J. Math. Oxf. 18, 369–384 (1967; Zbl 0168.26205)] proved that \(|\mathcal{F}| \leq \smash{\binom{n - 1}{k - 1}} - \smash{\binom{n - k - 1}{k - 1}} + 1\) if \(\mathcal{F}\) is nontrivial and intersecting. We provide a proof by injection of this result.

MSC:

05D05

Extremal set theory

Keywords:

finite sets; intersection; hypergraphs

Citations:

Zbl 0168.26205

References:

[1]	10.1093/qmath/12.1.313 · Zbl 0100.01902
[2]	; Frankl, Combinatorics, I : Proc. Fifth Hungarian Colloq.. Combinatorics, I : Proc. Fifth Hungarian Colloq.. Colloq. Math. Soc. János Bolyai, 18, 365, (1978)
[3]	10.1016/0097-3165(87)90005-7 · Zbl 0661.05002
[4]	; Frankl, Surveys in combinatorics 1987. Surveys in combinatorics 1987. London Math. Soc. Lecture Note Ser., 123, 81, (1987)
[5]	10.1016/0097-3165(86)90121-4 · Zbl 0583.05002
[6]	10.1016/0097-3165(92)90054-X · Zbl 0767.05093
[7]	10.1093/qmath/18.1.369 · Zbl 0168.26205
[8]	10.1016/j.disc.2018.03.010 · Zbl 1384.05151
[9]	; Katona, Theory of graphs, 187, (1968)
[10]	; Kruskal, Mathematical optimization techniques, 251, (1963)
[11]	10.1016/j.jcta.2017.11.006 · Zbl 1377.05190
[12]	10.1007/BF02582941 · Zbl 0588.05014