Zarankiewicz problem

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


Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Look at other dictionaries:

  • Kazimierz Zarankiewicz — (2 May 1902 5 September 1959) was a Polish mathematician. He was born in Częstochowa and died in London, England.His main interest was topology. He studied at the University of Warsaw, together with Zygmunt Janiszewski, Stefan Mazurkiewicz,… …   Wikipedia

  • Mountain climbing problem — Example of the problem resolution. In mathematics, the mountain climbing problem is a problem of finding conditions two function forming profiles of a two dimensional mountain must satisfy, so that two climbers can start on the bottom on the… …   Wikipedia

  • List of mathematics articles (Z) — NOTOC Z Z channel (information theory) Z factor Z function Z group Z matrix (mathematics) Z notation Z order (curve) Z test Z transform Z* theorem Zadoff–Chu sequence Zahorski theorem Zakai equation Zakharov–Schulman system Zakharov system ZAMM… …   Wikipedia

  • Extremal graph theory — is a branch of mathematics. In the narrow sense, extremal graph theory studies the graphs which are extremal among graphs with a certain property. There are various meanings for the word extremal : with the largest number of edges, the largest… …   Wikipedia

  • Crossing number (graph theory) — A drawing of the Heawood graph with three crossings. This is the minimum number of crossings among all drawings of this graph, so the graph has crossing number cr(G) = 3. In graph theory, the crossing number cr(G) of a graph G is the… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”