Quelltext der Seite 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 <math>\{1,2,3,\ldots,n\}</math> für <math>n \in \mathbb N</math>.

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

== Bemerkungen ==
Eine <math>k</math>-Schnittfamilie, für die Gleichheit gilt, ist die Menge aller <math>k</math>-Mengen, die ein fixiertes Element <math>s</math> der <math>n</math>-Menge enthalten.

Einen ''einfachen'' Beweis liefert G. O. H. Katona im Journal of Combinatorial Theory (B).<ref>Journal of Combinatorial Theory (B) 13, 183–184 (1972).</ref> Dieser Beweis erfolgt durch [[doppeltes Abzählen]]. Der Originalbeweis von 1961 verwendete [[Vollständige Induktion|Induktion]] über n.

Der Fall <math>n < 2k</math> ist trivial, denn dann haben je zwei <math>k</math>-Mengen einen nichtleeren Schnitt und man erhält <math>|F| \le \binom nk</math>.

[[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.<ref>[[Paul Erdős]]: ''My joint work with Richard Rado.'' Surveys of Combinatorics, Cambridge 1987, S.&nbsp;53–80.</ref>

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

[[Kategorie:Satz (Mengenlehre)|ErdosKoRado, Satz von]]
[[Kategorie:Paul Erdős]]