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) ${\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.