×

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

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

Citations:

Zbl 0168.26205
PDF BibTeX XML Cite
Full Text: DOI Euclid

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
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.