Zarankiewicz problem

From Wikipedia, the free encyclopedia

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 Z3(n) (defined below) for n \le 6.

Contents

[edit] Definition

Let

Ka,b

denote a complete bipartite graph. Define

Zr,s(m,n)

to be the smallest integer k such that every subgraph of

Km,n

with k edges contains a subgraph isomorphic to

Kr,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

Zr(n): = Zr,r(n,n).

[edit] Examples

Claim: Z2(3) = 7.

Proof: Figure A below is an example of a subgraph of K3,3 with 6 edges that does not contain any copies of K2,2, so Z2(3) > 6. However, any subgraph of K3,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 K2,2 (marked in red), so Z2(3) = 7.

Figure A
Enlarge
Figure A
Figure B
Enlarge
Figure B
Figure C
Enlarge
Figure C


[edit] Inequalities

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

Z_{r,s}(m,n)\le (s-1)^{1/t}(n-t+1)m^{1-1/t}+(t-1)m

However, 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.


[edit] Asymptotic Bounds

  • Z_2(n) \in \Theta(n^{3/2})


[edit] See also

  • 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