Satz von Erdős-Ko-Rado

Der Satz von Erdős-Ko-Rado ist ein Satz aus der Mengenlehre. Er ist benannt nach seinen Autoren Paul Erdős, Richard Rado und Chao Ko. Der Satz gibt eine obere Grenze für die Mächtigkeit einer k-Schnittfamilie (k-uniform intersecting family) in einer n-Menge $\{1,2,3,\ldots ,n\}$ für $n\in \mathbb {N}$.

Aussage

Die Mächtigkeit einer $k$-Schnittfamilie $F$ in einer $n$-Menge ist beschränkt durch $|F|\leqslant {\binom {n-1}{k-1}}$ für $n\geqslant 2k$.

Bemerkungen

Eine $k$-Schnittfamilie, für die Gleichheit gilt, ist die Menge aller $k$-Mengen, die ein fixiertes Element $s$ der $n$-Menge enthalten.

Einen einfachen Beweis liefert G. O. H. Katona im Journal of Combinatorial Theory (B). Dieser Beweis erfolgt durch doppeltes Abzählen. Der Originalbeweis von 1961 verwendete Induktion über n.

Der Fall $n<2k$ ist trivial, denn dann haben je zwei $k$-Mengen einen nichtleeren Schnitt und man erhält $|F|\leq {\binom {n}{k}}$.

Paul Erdős, Richard Rado und Chao Ko veröffentlichten den Satz 1961, er wurde jedoch bereits 1938 während des gemeinsamen Aufenthalts der Autoren in Cambridge formuliert. Als Grund für diese lange Zeitdifferenz gibt Erdős das mangelnde Interesse an Kombinatorik in jener Zeit an.

Quellen

• Martin Aigner, Günter M. Ziegler: Das BUCH der Beweise, Springer, Berlin 2002, ISBN 3-540-42535-7 (3. Auflage: ISBN 978-3-642-02258-6).
• Paul Erdős: My joint work with Richard Rado. Surveys of Combinatorics, Cambridge 1987, S. 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.