Lemma von Corrádi

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

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

Seien ${\displaystyle n,r,N}$ natürliche Zahlen und ${\displaystyle k}$ eine ganze Zahl mit ${\displaystyle n\geq r\geq k\geq 0}$ .

Sei ${\displaystyle H=(X,{\mathcal {A}})}$ ein uniformer Hypergraph, bestehend aus einer Knotenmenge ${\displaystyle X}$ mit ${\displaystyle n}$ Knoten und einer ${\displaystyle N}$-gliedrigen Familie ${\displaystyle {\mathcal {A}}=(A_{1},A_{2},\ldots ,A_{N})}$ von Hyperkanten mit jeweils ${\displaystyle r}$ Knoten.

Sei weiter vorausgesetzt, dass für alle Durchschnitte ${\displaystyle A_{i}\cap A_{j}\;(i,j=1,2,\ldots ,N)}$ je zweier Hyperkanten stets die Anzahlbedingung ${\displaystyle |A_{i}\cap A_{j}|\leq k}$ gegeben sei.

Dann gilt:

(*) ${\displaystyle n\geq {\frac {Nr^{2}}{r+(N-1)k}}}$.

Beweis

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) ${\displaystyle d(x):={\deg _{H}}(x)=|\{i\in \{1,2,\ldots ,N\}\colon x\in A_{i}\}|\;(x\in X)}$

(2) ${\displaystyle J_{Y}:=\{(y,i)\in Y\times \{1,2,\ldots ,N\}\colon y\in A_{i}\}\;(Y\subseteq X)}$

(3) ${\displaystyle K:=\{(x,i,j)\in X\times \{1,2,\ldots ,N\}\times \{1,2,\ldots ,N\}\colon x\in A_{i}\cap A_{j}\}}$

Doppeltes Abzählen

(4) ${\displaystyle |J_{Y}|=\sum _{y\in Y}{d(y)}=\sum _{j=1}^{N}{|Y\cap A_{j}|}\;(Y\subseteq X)}$

(5) ${\displaystyle |K|=\sum _{x\in X}{d(x)^{2}}=\sum _{i,j=1}^{N}{|A_{i}\cap A_{j}|}=\sum _{i=1}^{N}{|J_{A_{i}}|}}$

Abschätzung nach oben

Mit (4) ergibt sich insbesondere für ${\displaystyle i=1,2,\ldots ,N}$:

(6) ${\displaystyle |J_{A_{i}}|=\sum _{j=1}^{N}{|A_{i}\cap A_{j}|}=|A_{i}|+\sum _{j=1,2,\ldots ,N \atop \;i\neq j}{|A_{i}\cap A_{j}|}\leq r+(N-1)k}$

Also folgt aus (5) und (6):

(7) ${\displaystyle \sum _{x\in X}{d(x)^{2}}\leq {N{\bigl (}r+(N-1)k{\bigr )}}}$

Abschätzung nach unten

Vermöge der jensenschen Ungleichung ergibt sich:

(8) ${\displaystyle \sum _{x\in X}{d(x)^{2}}=n\cdot \sum _{x\in X}{{\frac {1}{n}}\cdot d(x)^{2}}\geq n\cdot {\bigl (}\sum _{x\in X}{{\frac {1}{n}}\cdot d(x)}{\bigr )}^{2}=n\cdot {\frac {1}{n^{2}}}\cdot {\bigl (}\sum _{x\in X}{d(x)}{\bigr )}^{2}={\frac {1}{n}}\cdot {\bigl (}\sum _{x\in X}{d(x)}{\bigr )}^{2}}$

Wiederum mit (4) und ${\displaystyle Y=X}$ folgt dann:

(9) ${\displaystyle \sum _{x\in X}{d(x)^{2}}\geq {\frac {1}{n}}\cdot {|J_{X}|}^{2}={\frac {1}{n}}\cdot {\bigl (}\sum _{j=1}^{N}{|A_{j}|}{\bigr )}^{2}={\frac {(Nr)^{2}}{n}}={\frac {N^{2}r^{2}}{n}}}$

Zusammenfassung

(7) und (9) zusammen ergeben dann:

(10) ${\displaystyle {N{\bigl (}r+(N-1)k{\bigr )}}\geq {\frac {N^{2}r^{2}}{n}}}$

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

Zusatz

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

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

• K. Corrádi: Problem at Schweitzer competition. In: Matematikai Lapok. Band 20, 1969, S. 159–162. 
• Stasys Jukna: Extremal Combinatorics (= Texts in Theoretical Computer Science). 2. Auflage. Springer Verlag, Heidelberg, Dordrecht, London, New York 2011, ISBN 978-3-642-17363-9 (MR2865719). 
• László Lovász: Combinatorial Problems and Exercises (= Texts in Theoretical Computer Science). North-Holland Publishing Company, Amsterdam, New York, Oxford 1979, ISBN 0-444-85219-0 (MR0537284). 
• Gábor J. Székely (Hrsg.): Contests in Higher Mathematics. Miklós Schweitzer Competitions 1962-1991 (= Problem Books in Mathematics). Springer Verlag, New York (u. a.) 1996, ISBN 0-387-94588-1 (MR1416130). 

Einzelnachweise

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