Zarankiewicz problem

In the mathematical field of extremal graph theory, the Zarankiewicz problem asks how many edges can be added to a bipartite graph while avoiding a specific bipartite subgraph. Initially, the Polish mathematician K. Zarankiewicz proposed the problem of determining the values of the function $Z\_3(n)$ (defined below) for $n\; le\; 6$.

Definition

Let

:$K\_\{a,b\}$

denote a complete bipartite graph. Define

:$Z\_\{r,s\}(m,n)$

to be the smallest integer "k" such that every subgraph of

:$K\_\{m,n\}$

with "k" edges contains a subgraph isomorphic to

:$K\_\{r,s\}$. An alternative and equivalent definition is as the smallest integer "k" such that every (0,1)-matrix of size "m"×"n" with "k" 1's must have a set of "r" rows and "s" columns such that the corresponding "r"×"s" submatrix is made up only of 1's.

For the specific case when $m\; =\; n$ and $r\; =\; s$, we define

:$Z\_r(n)\; :=\; Z\_\{r,r\}(n,n)$.

Examples

Claim: $Z\_2(3)\; =\; 7$.

Proof:Figure A below is an example of a subgraph of $K\_\{3,3\}$ with "6" edges that does not contain any copies of $K\_\{2,2\}$, so $Z\_2(3)\; >\; 6$.However, any subgraph of $K\_\{3,3\}$ with "7" edges must look like the graph in either Figure B or Figure C (up to isomorphism), and both graphs contain a copy of $K\_\{2,2\}$ (marked in red), so $Z\_2(3)\; =\; 7$.

Inequalities

The following upper bound was established by Kövari, Sós and Turán shortly after the problem had been posed:

:$Z\_\{r,s\}(m,n)le\; (s-1)^\{1/t\}(n-t+1)m^\{1-1/t\}+(t-1)m$

Except for some specific values of "r" and "s", it is not known whether this bound is essentially optimal. Nevertheless, some progress on this question has been made on this question in the last fifty years. For an overview of early work, see chapter VI.2 in Bollobás' book, and of more recent results, consult e.g. Füredi's papers on the topic mentioned below.

= Asymptotic Bounds =

* $Z\_2(n)\; in\; Theta(n^\{3/2\})$

See also

References

* Bollobás: Extremal Graph Theory, Academic Press, 1978

* Füredi, New asymptotics for bipartite Turán numbers, J. Combinatorial Theory, Series A 75 1996, pp. 141-144.

* Füredi, An upper bound on Zarankiewicz' problem, Comb. Prob. Computing 5, 1996, pp. 29-33

* Kövari, Sós and Turán: On a problem of K. Zarankiewicz, Colloq. Math. 3, 1954, pp. 50-57