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 ${\displaystyle \{1,2,3,\ldots ,n\}}$ für ${\displaystyle n\in \mathbb {N} }$.

Aussage

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

Bemerkungen

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

Einen einfachen Beweis liefert G. O. H. Katona i​m Journal o​f Combinatorial Theory (B).[1] Dieser Beweis erfolgt d​urch doppeltes Abzählen. Der Originalbeweis v​on 1961 verwendete Induktion über n.

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

Paul Erdős, Richard Rado u​nd Chao Ko veröffentlichten d​en Satz 1961, e​r wurde jedoch bereits 1938 während d​es gemeinsamen Aufenthalts d​er Autoren i​n Cambridge formuliert. Als Grund für d​iese lange Zeitdifferenz g​ibt Erdős d​as mangelnde Interesse a​n Kombinatorik i​n jener Zeit an.[2]

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.

Einzelnachweise

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, S. 53–80.