Lemma von Corrádi

Das Lemma von Corrádi, Vorlage:EnS, 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.

Formulierung des Lemmas

Im Einzelnen besagt das Lemma Folgendes:

Seien $n,r,N$ natürliche Zahlen und $k$ eine ganze Zahl mit $n\ge r\ge k\ge 0$ .

Sei $H=(X,𝒜)$ ein uniformer Hypergraph, bestehend aus einer Knotenmenge $X$ mit $n$ Knoten und einer $N$-gliedrigen Familie $𝒜=(A_1,A_2,\dots ,A_N)$ von Hyperkanten mit jeweils $r$ Knoten.

Sei weiter vorausgesetzt, dass für alle Durchschnitte $A_i\cap A_j(i,j=1,2,\dots ,N)$ je zweier Hyperkanten stets die Anzahlbedingung $|A_i\cap A_j|\le k$ gegeben sei.

Dann gilt:

(*) $n\ge \frac{N{r}^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:

Festlegungen

(1) $d(x):={\mathrm{deg}}_H(x)=|\{i\in \{1,2,\dots ,N\}:x\in A_i\}|(x\in X)$

(2) $J_Y:=\{(y,i)\in Y\times \{1,2,\dots ,N\}:y\in A_i\}(Y\subseteq X)$

(3) $K:=\{(x,i,j)\in X\times \{1,2,\dots ,N\}\times \{1,2,\dots ,N\}:x\in A_i\cap A_j\}$

Doppeltes Abzählen

(4) $|J_Y|=\sum _{y\in Y}d(y)=\sum _{j=1}^N|Y\cap A_j|(Y\subseteq X)$

(5) $|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 $i=1,2,\dots ,N$:

(6) $|J_{A_i}|=\sum _{j=1}^N|A_i\cap A_j|=|A_i|+\sum _{\genfrac{}{}{0ex}{}{j=1,2,\dots ,N}{i\ne j}}|A_i\cap A_j|\le r+(N-1)k$

Also folgt aus (5) und (6):

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

Abschätzung nach unten

Vermöge der jensenschen Ungleichung ergibt sich:

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

Wiederum mit (4) und $Y=X$ folgt dann:

(9) $\sum _{x\in X}d(x{)}^2\ge \frac{1}{n}\cdot {|J_X|}^2=\frac{1}{n}\cdot (\sum _{j=1}^N|A_j|{)}^2=\frac{(Nr{)}^2}{n}=\frac{N^2{r}^2}{n}$

Zusammenfassung

(7) und (9) zusammen ergeben dann:

(10) $N(r+(N-1)k)\ge \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.

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.

Quellen und Hintergrundliteratur

• Vorlage:Literatur
• Vorlage:Literatur
• Vorlage:Literatur
• Vorlage:Literatur