Zarankiewicz problem

Remarks

Equivalently, consider bipartite graphs with parts $A$ and $B$ of sizes $m$ and $n$. Then $z(m, n; s, t)$ is the largest number of edges of such a graph with no complete bipartite subgraph $K_{s,t}$ that has $s$ vertices in $A$ and $t$ in $B$. It is closely tied to the extremal number $\mathrm{ex}(n, K_{s,t})$.

The Kővári–Sós–Turán theorem gives the upper bound $z(n, n; t, t) = O(n^{2 - 1/t})$ for fixed $t$. For $s = t = 2$ the order $n^{3/2}$ is correct. If $q$ is a prime power and $n = q^2 + q + 1$, then $z(n, n; 2, 2) = (q + 1)(q^2 + q + 1)$, and the incidence matrix of a finite projective plane of order $q$ attains this value. The order $n^{2 - 1/t}$ is also known to be correct for $t = 3$ and, for $z(n, n; s, t)$, when $s$ is large enough compared with $t$, by algebraic constructions called norm graphs. In general the problem is open; for example, the order of growth of $z(n, n; 4, 4)$ is not known.