Satz von Erdős-Ko-Rado

aus Wikipedia, der freien Enzyklopädie
(Weitergeleitet von Satz von Erdös-Ko-Rado)
Wechseln zu: Navigation, Suche

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[Bearbeiten]

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[Bearbeiten]

Ein 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).[1] 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| \le \binom nk.

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.[2]

Quellen[Bearbeiten]

Einzelnachweise[Bearbeiten]

  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.