Satz von Erdős-Ko-Rado

mathematischer Satz

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 .

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

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.