## [Erdős–Ko–Rado-Satz](/de/node/61272) Definition Bestimmt die maximale Kardinalität einer Familie von k-Element-Teilmengen einer n-Element-Menge, sodass jedes Paar von Teilmengen eine nichtleere Schnittmenge hat; in der klassischen Form ist für n ≥ 2k die maximale Größe die Anzahl der k-Teilmengen, die ein festes Element enthalten. ## Prinzip Prinzip Ein extremal-kombinatorisches Prinzip: Unter der Bedingung paarweiser Schnittmenge sind optimale Familien stark strukturiert (typischerweise 'Sterne'), und Verschiebungs‑/Kompressionsverfahren liefern die scharfen Schranken. ## Demonstration Demonstration Beispiel: Für n = 8 und k = 3 mit n ≥ 2k ist die maximale Größe einer intersecting family die Zahl der 3-Teilmengen, die ein festes Element enthalten, also C(7,2) = 21; eine maximale Familie erhält man, indem man ein Element festhält und alle k-Mengen nimmt, die es enthalten. ## Fehlanwendung Fehlanwendung Die klassische Schranke anwenden, wenn n < 2k gilt, oder auf nicht-uniforme Familien ohne Anpassung; die gleiche extremale Struktur für t-intersecting Families (Schnittgröße ≥ t) anzunehmen, ohne die passende Verallgemeinerung. ## Konsequenz Konsequenz Ist die Voraussetzung erfüllt, liefert der Satz eine scharfe obere Schranke und eine strukturelle Charakterisierung der Extremal-Familien (Sterne), was Beweise und Konstruktionen in Problemen zu intersecting families leitet. ## Umkehrung Umkehrung Die umgekehrte Perspektive betrachtet paarweise disjunkte Familien: Maximierung unter Disjunktheitsbedingungen führt zu anderen Maxima und Konstruktionen (Matching), und zeigt, wie Umkehrung der Schnittbedingung optimale Familien verändert. ## Abgrenzung Abgrenzung Gilt für uniforme Familien von k-Teilmengen einer n-Menge; die klassische Schranke verlangt n ≥ 2k, damit der Stern extremal ist; für n < 2k, t-intersecting Bedingungen oder nicht-uniforme Sammlungen sind Varianten erforderlich. ## Semantische Spannung Semantische Spannung Im Wettbewerb mit benachbarten Aussagen wie Sätzen über t-intersecting Familien oder dem vollständigen Schnittsatz von Ahlswede–Khachatrian; die Spannung besteht zwischen 'intersecting' im Sinne nichtleerer Schnittmenge und stärkeren Schnittgrößenbedingungen, die die extremale Struktur verändern. ## Synthese Synthese Erdős–Ko–Rado gibt die maximale Größe und Struktur einer uniformen Familie mit paarweiser Schnittbedingung an: Unter der klassischen Bedingung n ≥ 2k sind die maximalen Familien diejenigen, die ein gemeinsames Element festlegen (Sterne), und Kompressionsmethoden liefern die Begründung.