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 für .

Aussage[Bearbeiten | Quelltext bearbeiten]

Die Mächtigkeit einer k-Schnittfamilie in einer n-Menge ist beschränkt durch für .

Bemerkungen[Bearbeiten | Quelltext bearbeiten]

Ein k-Schnittfamilie, für die Gleichheit gilt, ist die Menge aller k-Mengen, die ein fixiertes Element 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 ist trivial, denn dann haben je zwei k-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.[2]

Quellen[Bearbeiten | Quelltext bearbeiten]

Einzelnachweise[Bearbeiten | Quelltext 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.