Zarankiewicz’s Problem |

Kazimierz Zarankiewicz

Zarankiewicz’s problem plays an important role in extremal combinatorics. Let’s first learn few things about Kazimierz Zarankiewicz from Wikipedia. Unfortunately, his life had a lot of suffering. He had to live the nightmare of concentration camps during World War II and he was a revolutionary. He was not a guerrilla but continued to teach despite the Nazi orders. Here is what Kuratowski writes about academic life during that period :

Almost all our professors of mathematics lectured at these clandestine universities, and quite a few of the students then are now professors or docents themselves. Due to that underground organisation, and in spite of extremely difficult conditions, scientific work and teaching continued, though on a considerably smaller scale of course. The importance of clandestine education consisted among others in keeping up the spirit of resistance, as well as optimism and confidence in the future, which was so necessary in the conditions of occupation. The conditions of a scientist’s life at that time were truly tragic. Most painful were the human losses.

Unfortunately, Zarankiewicz died young. This post is about part of the legacy he left to us.

Zarakniewicz’s problem: At most how many 1’s can a a $n \times n$ 0-1 matrix contain if it has not $a \times b$ submatrix whose entries are all 1’s?

This problem can be reformulated in terms of bipartite graphs. Let $G(V_1,V_2,E), V_1=V_2=[n]$ be a $n \times n$ bipartite graph. Here we discuss the following version of the problem: find $k_{a}(n)=$ minimum $k$ such that any bipartite graph $G([n],[n],E)$ with $|E|=k$ has a $a \times a$ bipartite clique.

Lower bound: I will obtain a lower bound using the probabilistic method. You should make things more formal that what I have them here, but the idea is correct. Consider $K_{n,n}$ the complete bipartite clique and let $p$ be a probability of keeping an edge, using independent coin tosses. We use the first moment to find the threshold value $p^*$ . What is the expected number of cliques $a \times a$ ? Let $X$ be the random variable of surviving such cliques after we toss our coin $n^2$ times. Clearly, $E[X] = {n \choose a} {n \choose a} p^{a^2} \approx (n^2 p^a)^a$ and therefore $p^*=n^{-2/a}$ . Hence the lower bound should be $p^* \times n^2 = n^{2-2/a}$ .

I would like to ask you to pay attention to the upper bound on $k_a(n)$ since the proof is a double counting argument which is known among Combinatorialists as Zarankiewicz counting. The argument is due to Kővári, Sós and Turán.

Upper bound: Assume there is no $a \times a$ bipartite clique in $G$ . We double count stars with $a$ leaves where the center of the star is a vertex in $[n]$. How many such stars are there? Let $\Delta$ be their number. Then $\Delta = \sum_{x \in V_1} {deg(x) \choose a} \geq n {|E|/n \choose a}$ . We used the convexity of the binomial coefficient and Jensen’s inequality. Now if we count $\Delta$ from the side of $V_2$ then clearly since we do not have any $a \times a$ cliques $\Delta \leq {n \choose a} (a-1)$ . Working out the details which is left as an exercise to you, [I guess you are interested if you reached this point of the post by reading sequentially :-)], we obtain $k_a(n) \leq (a-1)^{1/a}n^{2-1/a}+(a-1)n$ . QED

I would like to mention something that may be some readers of this blog may not be familiar with. How is a binomial coefficient ${x \choose k}$ defined when $x$ is real? Well it is possible, and here is the definition as you would expect it. ${x \choose k} = \frac{x(x-1)..(x-k+1)}{k!}$ . But how can it be a convex function? Well, it has $k$ zeros obviously so it is natural to wonder. But it is not a real problem. Think why as the riddle of the day!