The problem of Zarankiewicz

Definition 6..15 (Zarankiewicz problem, $ z(n;t)$)  

The bipartite analogue of Turán's problem is to find the maximum number of edges $ z(n;t)$ in an $ (n,n)$-bipartite graph not containing a subgraph $ K_{t,t}$.

The value of $ z(n;t)$ is not known.

Theorem 6..16 (Zarankiewicz)  

Let $ y = \frac{1}{n} z(n;t)$. Then $ {y \choose t} \le \frac{t-1}{n}{n \choose t}$.



John Fremlin 2010-02-17