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 .
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.
[edit] Inequalities
The following upper bound was established by Kövari, Sós and Turán shortly after the problem has been posed:
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
[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