Another simple proof of a theorem of Milner (Q1304631)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Another simple proof of a theorem of Milner |
scientific article |
Statements
Another simple proof of a theorem of Milner (English)
0 references
4 June 2000
0 references
A theorem of Milner states that if \(F\) is a family of subsets of \(\{1,\dots, n\}\) such that \(A\cap B\neq\varnothing\) and \(A\not\subset B\) for all \(A,B\in F\) then \(|F|\leq\left(\begin{smallmatrix} n\\ \lceil{n+1\over 2}\rceil\end{smallmatrix}\right)\). The author presents a proof of this theorem using the standard shifting technique and the cycle method applied to the two middle levels.
0 references
Sperner family
0 references
intersecting family
0 references
theorem of Milner
0 references
shifting technique
0 references
cycle method
0 references