A Katona-type proof of an Erdős-Ko-Rado-type theorem (Q2566804): Difference between revisions

Let \(k \leq n/2\), and suppose that a family \(A\) of \(k\)-sets contained in \(\{ 1, 2, \dots, n\}\) is an intersecting family, that is, any two sets in \(A\) have a non-empty intersection. The Erdős-Ko-Rado theorem asserts that (1) \(| A| \leq \binom{ n-1 }{ k-1 }\) and (2) if \(| A| = \binom{ n-1 }{ k-1 }\) then \(A\) contains all \(k\)-sets that contain a fixed \(j\) (\(1 \leq j \leq n\)). The author gives a simple proof of an analogue, due to Dinur and Safra, of the Erdős-Ko-Rado theorem, using an idea of Katona.