Lemma from Corrádi

The lemma Corradi , English Corradi's lemma , named after the Hungarian mathematician Kereszyély Corradi is a theorem that the transition field of the mathematical part areas combinatorics , Graph Theory and finite geometry is attributable. The lemma provides information about the minimum number of nodes that a finite uniform hypergraph must have, if it is assumed that two different hyper-edges have a certain number of nodes in common .

Formulation of the lemma

In detail, the lemma says:

Be natural numbers and be an integer with . ${\displaystyle n,r,N}$ ${\displaystyle k}$ ${\displaystyle n\geq r\geq k\geq 0}$

Let be a uniform hypergraph, consisting of a set of nodes with nodes and a - membered family of hyperedges with nodes each . ${\displaystyle H=(X,{\mathcal {A}})}$ ${\displaystyle X}$ ${\displaystyle n}$ ${\displaystyle N}$ ${\displaystyle {\mathcal {A}}=(A_{1},A_{2},\ldots ,A_{N})}$ ${\displaystyle r}$

Let it be further assumed that the number condition is always given for all intersections of two hyperedges . ${\displaystyle A_{i}\cap A_{j}\;(i,j=1,2,\ldots ,N)}$ ${\displaystyle |A_{i}\cap A_{j}|\leq k}$

Then:

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

proof

The proof of the inequality (*) results - in connection with the representation by Jukna and Lovász - by applying the method of double counting and the other inequality in the following steps:

Determinations

(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}\}}$

Double counting

(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}}|}}$

Upward estimate

With (4) results in particular for : ${\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}$

So it follows from (5) and (6) :

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

Downward estimate

By virtue of those inequality we get:

(8th) ${\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}}$

Again with (4) and then follows: ${\displaystyle Y=X}$

(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}}}$

Summary

(7) and (9) together then result in:

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

Since (10) and (*) are equivalent, everything is shown.

additive

The above inequality (*) is sharp in the sense that finite structures exist for which in the inequality (*) even the equal sign applies. An example of this is offered by every finite projective plane in which one understands its points as nodes and its straight lines as hyper-edges of a hypergraph.

Note on the history

The lemma goes back to a problem that K. Corrádi posed on the occasion of the 1968 Miklós Schweitzer competition for students .

Sources and background literature

• K. Corrádi: Problem at Schweitzer competition . In: Matematikai Lapok . tape 20 , 1969, p. 159-162 .
• Stasys Jukna: Extremal Combinatorics (=  Texts in Theoretical Computer Science ). 2nd Edition. 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 (Ed.): Contests in Higher Mathematics . Miklós Schweitzer Competitions 1962-1991 (=  Problem Books in Mathematics ). Springer Verlag, New York (et al.) 1996, ISBN 0-387-94588-1 . MR1416130

Individual evidence

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