Erdős-Ko-Rado's theorem

The Erdős-Ko-Rado theorem is a set of the set theory . It is named after its authors Paul Erdős , Richard Rado and Chao Ko. The set is an upper limit for the thickness a k- average family (k-uniform intersecting family) in an n-set for . ${\displaystyle \{1,2,3,\ldots ,n\}}$ ${\displaystyle n\in \mathbb {N} }$

statement

The thickness of a k-cut family in an n-set is limited by for . ${\displaystyle F}$ ${\displaystyle |F|\leqslant {\binom {n-1}{k-1}}}$ ${\displaystyle n\geqslant 2k}$

Remarks

A k-cut family for which equality holds is the set of all k-sets that contain a fixed element of the n-set. ${\displaystyle s}$

GOH Katona provides a simple proof in the Journal of Combinatorial Theory (B). This proof is done by counting twice . The original 1961 evidence used induction on n.

The case is trivial, because then every two k-sets have a non-empty cut and one obtains . ${\displaystyle n<2k}$ ${\displaystyle |F|\leq {\binom {n}{k}}}$

Paul Erdős , Richard Rado and Chao Ko published the sentence in 1961, but it was formulated as early as 1938 during the authors' stay in Cambridge . Erdős cites the lack of interest in combinatorics at that time as the reason for this long time difference.

swell

• Martin Aigner , Günter M. Ziegler : The Book of Evidence , Springer, Berlin 2002, ISBN 3-540-42535-7 (3rd edition: ISBN 978-3-642-02258-6 ).
• Paul Erdős : My joint work with Richard Rado. Surveys of Combinatorics, Cambridge 1987, pp. 53-80.
• Stasys Junka : Extremal Combinatorics. Springer, Berlin 2001, ISBN 3-540-66313-4 .
• Paul Erdős , Richard Rado , Chao Ko : Intersection theorems for systems of finite sets. Quarterly Journal of Mathematics, Oxford Series (1961), series 2 12: 313-320.

Individual evidence

1. ↑ Journal of Combinatorial Theory (B) 13, 183-184 (1972).
2. ^ Paul Erdős : My joint work with Richard Rado. Surveys of Combinatorics, Cambridge 1987, pp. 53-80.