A Katona-type proof of an Erdős-Ko-Rado-type theorem (Q2566804)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A Katona-type proof of an Erdős-Ko-Rado-type theorem |
scientific article |
Statements
A Katona-type proof of an Erdős-Ko-Rado-type theorem (English)
0 references
28 September 2005
0 references
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.
0 references
intersecting family
0 references
extremal set theory
0 references