Das Lemma von Corrádi, englisch Corrádi's lemma, benannt nach dem ungarischen Mathematiker Keresztély Corrádi, ist ein Lehrsatz, welcher dem Übergangsfeld der mathematischen Teilgebiete Kombinatorik, Graphentheorie und Endliche Geometrie zuzurechnen ist. Das Lemma gibt Aufschluss über die mindestens notwendige Anzahl der Knoten, die ein endlicher uniformer Hypergraph haben muss, wenn vorausgesetzt wird, dass je zwei verschiedene Hyperkanten eine gewisse vorgegebene Anzahl von Knoten gemeinsam haben.[1][2]

Formulierung des Lemmas

Bearbeiten

Im Einzelnen besagt das Lemma Folgendes:[1][2]

Seien   natürliche Zahlen und   eine ganze Zahl mit   .
Sei   ein uniformer Hypergraph, bestehend aus einer Knotenmenge   mit   Knoten und einer  -gliedrigen Familie   von Hyperkanten mit jeweils   Knoten.
Sei weiter vorausgesetzt, dass für alle Durchschnitte   je zweier Hyperkanten stets die Anzahlbedingung   gegeben sei.
Dann gilt:
(*)  .

Der Beweis der Ungleichung (*) ergibt sich – in Anschluss an die Darstellung bei Jukna und Lovász – durch Anwendung der Methode des doppelten Abzählens und der jensenschen Ungleichung in folgenden Schritten:[1][2]

Festlegungen
(1)  
(2)  
(3)  
Doppeltes Abzählen
(4)  
(5)  
Abschätzung nach oben

Mit (4) ergibt sich insbesondere für  :

(6)  

Also folgt aus (5) und (6):

(7)  
Abschätzung nach unten

Vermöge der jensenschen Ungleichung ergibt sich:

(8)  

Wiederum mit (4) und   folgt dann:

(9)  
Zusammenfassung

(7) und (9) zusammen ergeben dann:

(10)  

Da nun (10) und (*) gleichwertig sind, ist alles gezeigt.

Die obige Ungleichung (*) ist scharf in dem Sinne, dass endliche Strukturen existieren, für welche in der Ungleichung (*) sogar das Gleichheitszeichen gilt. Ein Beispiel dafür bietet jede endliche projektive Ebene, indem man deren Punkte als Knoten und deren Geraden als Hyperkanten eines Hypergraphen auffasst.[3]

Anmerkung zur Historie

Bearbeiten

Das Lemma geht zurück auf ein Problem, welches K. Corrádi anlässlich des 1968er Miklós-Schweitzer-Wettbewerbs für Studenten gestellt hat.[4]

Quellen und Hintergrundliteratur

Bearbeiten

Einzelnachweise

Bearbeiten
  1. a b c Stasys Jukna: Extremal Combinatorics. 2011, S. 23, 37
  2. a b c László Lovász: Combinatorial Problems and Exercises. 1979, S. 78,130,446-447
  3. Stasys Jukna: Extremal Combinatorics. 2011, S. 37
  4. Gábor J. Székely: Contests in Higher Mathematics: Miklós Schweitzer Competitions 1962–1991. 1996, S. 10