This webpage is devoted to Zarankiewicz's Conjecture, an open problem in graph theory.

- There are sets A and B with #(A)=
*m*and #(B)=*n*. - Two vertices x and y share a common edge if and only if
*x*∈ A and*y*∈ B.

The

A

The

In regard to this definition we assume that:

- No edge intersects itself.
- Any two edges have at most one point in common. This can be either a crossing or a common vertex.
- And most importantly: Every point that is not a vertex, lies on at most two edges.

For a full account of this history, see "A Note of Welcome" by Paul Turán.

The proof Zarankiewicz gave was with induction. Guy showed that there was a wrong argument in the inductive step. This mistake had already been found by Ringel and Kainen in 1965 and 1966, as Guy acknowledges in his article.

This was also the beginning of another conjecture, similar to Zarankiewicz' conjecture, this time concerning complete graphs. This conjecture states that the crossing number of the complete graph K

Nonetheless, Zarankiewicz gave a construction for a drawing of K

If

If

Place the

If we now connect all points on the x-axis with all points on the y-axis, we get a drawing of K

- Guy's article had another interesting result. He showed that if the conjecture holds for
*m*and*n*both odd, then the conjecture also holds for*m+1*and*n+1*. The proof uses induction. Say the conjecture holds for*m*=2s-1 and Then K_{m+1,n}contains*m+1*copies of K_{m,n}, all of which contain s(s-1)⌊^{n}⁄_{2}⌋⌊^{n-1}⁄_{2}⌋ crossings. But now we counted each crossing more than once. Since each crossing comes from two edges both from the*m*+1 vertices to the*n*other vertices, it follows that cr(K_{m+1,n}) = ⌊^{n}⁄_{2}⌋⌊^{n-1}⁄_{2}⌋⌊^{m+1}⁄_{2}⌋⌊^{m}⁄_{2}⌋.

- In 1970 Daniel J. Kleitman published an article in the Journal of Combinatorial Theory
^{[4]}in which he gives restrictions on the crossing number of bipartite graphs. Furthermore, he proofs that cr(K_{5,n})=4⌊^{n}⁄_{2}⌋⌊^{n-1}⁄_{2}⌋ and that cr(K_{6,n})=6⌊^{n}⁄_{2}⌋⌊^{n-1}⁄_{2}⌋. That is, the conjecture holds for K_{5,n}and K_{6,n}for all*n*.

- After a long period without results Douglas R. Woodall verified Zarankiewicz conjecture for K
_{7,7}and K_{7,9}. In 1993 his article was published in the Journal of Graph Theory.

In this article he used the theory of cyclic-order graphs to write computer programs to verify the conjecture.

The*cyclic-order graph*, CO_{n}, is defined as the graph with vertices the (*n*-1)! cyclic orderings of a set V with*n*elements where two vertices are adjacent if one can be obtained from the other by transposing two adjacent elements. For example, in CO_{3}the orderings 021 and 201 are adjacent because we can get 201 by changing the order of 0 and 2.

- In Kleitman's article, there is a proof that the crossing number of the complete bipartite graph is bounded below by
^{1}⁄_{5}m(m-1)⌊^{n}⁄_{2}⌋⌊^{n-1}⁄_{2}⌋ for*m*≥5. to get this result he uses a several counting arguments, combined with his other results.

This gives the bound cr(K_{m,n}) ≥ 0.8⌊^{n}⁄_{2}⌋⌊^{n-1}⁄_{2}⌋⌊^{m}⁄_{2}⌋⌊^{m-1}⁄_{2}⌋ for*m*=5.

- This bound was improved by Nagi H. Nahas in his article "On the crossing number of K
_{m,n}"^{[6]}. This was published in 2003 in Electronic Journal of Combinatorics. This was only a minor improvement from Kleitman's bound, since this was improved to^{1}⁄_{5}m(m-1)⌊^{n}⁄_{2}⌋⌊^{n-1}⁄_{2}⌋+9.9×10^{-6}m^{2}n^{2}, for large enough*m*.

Nahas proofs that in any drawing of K_{m,n}there are certain non optimal drawings of the subgraph K_{5,n}and this improves the bound slightly. As Nahas himself also said: Perhaps non optimal drawing of other subgraphs will lead to even better bounds or even a proof of the conjecture.

- The last improvement on the lower bound of the crossing number is from De Klerk, Maharry, Pasechnik, Richter and Salazar. Their article "Improved bounds for the crossing numbers of K
_{m,n}and K_{n}", published in the Journal of Discrete Mathematics by SIAM in 2006^{[7]}, takes the lower bound up to 0.83m(m-1)⌊^{n}⁄_{2}⌋⌊^{n-1}⁄_{2}⌋.

- The first is a result from 1983 by Garey and Johnson. They published an article in SIAM Journal of Algebra and Discrete Mathematics proving that determining the crossing number of K
_{m,n}is an NP-hard problem^{[8]}, according to, for instance, [9]. This makes calculation of this number in general difficult. For more information about complexity classes see this site.

- When we consider only cubic graphs, the problem of calculating the crossing numbers is still NP-hard. This was first proved by Pter Hlinĕný in his article "Crossing number is hard for cubic graphs" in the Journal of Combinatorial Theory in 2006.

A*cubic graph*is a graph in which every vertex has degree three. That is, every vertex is adjacent with exactly three other vertices.

- Richter and Thomassen have proved a connection between cr(K
_{m,n}) and cr(K_{l}) in their article "Relations Between Crossing Numbers of Complete and Complete Bipartite Graphs". They published this in The American Mathematical Monthly in 1977^{[10]}.

First they show that the sequences^{cr(Kn)}⁄(^{n}_{4}) and^{cr(Kn,n)}⁄(^{n}_{2})^{2}both have a limit for*n*to ∞, defined as LC and LB respectively. Then they conclude that LC ≥^{3}⁄_{2}LB.

- Considering cr(K
_{n}), we can specify that we only always drawing of K_{n}with straight lines. This is called a*rectilineair drawing*of a graph. The first mathematicians to consider these rectilineair drawings were Harary and Hill^{[11]}. In their article published in 1963, they formulate the conjecture that the rectilineair crossing number of K_{n}, cr(K_{n}) is equal to cr(K_{n}) only for*n*∈ {1,2,3,4,5,6,7,9}. Their article also contains a rectilineair drawing of K_{8}with 19 crossings, which is one more than cr(K_{8}).

Considering cr(K_{m,n}) is not very exciting, because Zarankiewicz's construction already gives us a rectilineair drawing of K_{m,n}with ⌊^{n}⁄_{2}⌋⌊^{n-1}⁄_{2}⌋⌊^{m}⁄_{2}⌋⌊^{m-1}⁄_{2}⌋ crossings.

- Continuing the work of Harary and Hill, an article was published by Brodsky, Durocher and Gethner in which they proof that cr(K
_{10})=62. This article was published in 2000 in the Electronic Journal of Combinatorics^{[12]}.

- Finally, there is a result concerning the crossing number of K
_{m,n}when drawn on a torus. This result, again from Guy this time together with Jenkyns, was published in 1969. Their article, "The Toroidal Crossing Number of K_{m,n}" proves that the toroidal crossing number of K_{m,n}lies between^{1}⁄_{15}(^{m}_{2})(^{n}_{2}) and^{1}⁄_{6}(^{m-1}_{2})(^{n-1}_{2}). Where the lower bound only holds for sufficiently large*m*and*n*.

[2] K. Zarankiewicz. "On a Problem of P. Turán Concerning Graphs." Fund. Math. Vol. 41, pp. 137-145, 1954.

[3] R. K. Guy, "The decline and fall of Zarankiewicz's theorem";

[4] D. J. Kleitman "The Crossing Number of K

[5] D. R. Woodall, "Cyclic-order graphs and Zarankiewicz's crossing-number conjecture" J. Graph Th. 17 pp. 657–671, 1993.

[6] N. H. Nahas, "On the crossing number of K

[7] E. De Klerk, J. Maharry, D. V. Pasechnik, R. B. Richter, G. Salazar, "Improved bounds for the crossing numbers of K

[8]* M. R. Garey, D. S. Johnson, "Crossing number is NP-complete", SIAM J. Alg. Discr. Math. 4, pp. 312–316, 1983.

[9] P. Hlinĕný, "Crossing number is hard for cubic graphs", Journal of Combinatorial Theory, Series B 96, pp. 455–471, 2006.

[10] R. B. Richter, C. Thomassen, "Relations Between Crossing Numbers of Complete and Complete Bipartite Graphs", The American Mathematical Monthly, 104, No. 2 pp. 131-137, 1977

[11] F. Harary, A. Hill, "On the number of crossings in a complete graph",

[12] A. Brodsky, S. Durocher, E. Gethner, "The Rectilinear Crossing Number of K

[13] R. K. Guy, T. A. Jenkyns, "The Toroidal Crossing Number of K

References with a * were inaccessible.

This site is a project for the course Advanced Graph Theory.

Supervision by: Wieb Bosma.

Last update: August 6th 2010.