Where does the "Zarankiewicz's lemma" from?

288 Views Asked by At

In order to prove Turan's Theorem, someone introduced a lemma so called "Zarankiewicz's lemma":

If $G$ is a $k$-free graph, then there exists a vertex having degree at most $\displaystyle \lfloor \frac{k-2}{k-1}n\rfloor$.

But I couldn't found a paper writes about this lemma, and all the book I read seems doesn't quote this lemma.

So what's the original paper of this lemma?

1

There are 1 best solutions below

0
On

Just for the sake of self containment, I'll include the proof given in here. We assume $G$ is a finite graph of size $n$ with no complete subgraphs of degree $k$. Suppose, to the contrary, that every vertex has degree greater than $\left\lfloor \dfrac{k-2}{k-1}n\right\rfloor=M$.

Pick a vertex $v_1$, and consider its set of neighbours, $N(v_1)$. The hypothesis is that $|N(v_1)| >M$. Pick now a neighbour $v_2\in N(v_1)$. Then $N(v_1)\cap N(v_2)$ is nonempty, since its cardinality is at least

$$|N(v_1)|+|N(v_2)|-|N(v_1\cup v_2)| \geqslant 2(M+1)-n >0$$

Indeed, $2(M+1)-n > \dfrac{2k-4}{k-1}n-n=\dfrac{k-3}{k-1}n$, for we know $M+1>\frac{k-2}{k-1}n$. Picking $v_3$ in such intersection, we see the triple intersection has cardinality at least $$3(M+1)-2n>\frac{k-4}{k-1}n$$

We can do this until we get to an intersection of $k-1$ neighbour sets, since in such case this has cardinality $$(k-1)(M+1)-(k-2)n>\frac{k-k}{k-1}n=0$$

If we now pick $v_k\in N(v_1)\cap\cdots \cap N(v_{k-1})$ we obtain a complete $k$-subgraph.