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 für .
Aussage Bearbeiten
Die Mächtigkeit einer -Schnittfamilie in einer -Menge ist beschränkt durch für .
Bemerkungen Bearbeiten
Eine -Schnittfamilie, für die Gleichheit gilt, ist die Menge aller -Mengen, die ein fixiertes Element der -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 ist trivial, denn dann haben je zwei -Mengen einen nichtleeren Schnitt und man erhält .
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 Bearbeiten
- 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 Bearbeiten
- Journal of Combinatorial Theory (B) 13, 183–184 (1972).
- Paul Erdős: My joint work with Richard Rado. Surveys of Combinatorics, Cambridge 1987, S. 53–80.