Zarankiewicz's Conjecture

Zarankiewicz's Conjecture

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

Preliminary definitions

The complete bipartite graph, Km,n, is the graph with m+n points such that:
The complete graph, Kn, is the graph with n points such that every pair of vertices share a common edge.

A crossing in a graph is an intersection of two of its edges.

The crossing number of a graph G, cr(G), is the minimum number of crossings needed to draw G in the plane.
In regard to this definition we assume that: For example, a graph G is planar if and only if cr(G) = 0.

The conjecture

The crossing number of the complete bipartite graph Km,n is equal to ⌊n⁄2⌋⌊n-1⁄2⌋⌊m⁄2⌋⌊m-1⁄2⌋.

Origin

The problem concerning the minimum number of crossings in a graph is known as Turán's brick factory problem. Paul Turán was sent to labour service during the Second World War. In 1944 he was working at a brick factory near Budapest. There were a number of kilns, where the bricks were heated and a number of storage yards, where the bricks were stored. All kilns were connected to all yards by rail. On a crossing of two rails, the trucks often derailed, which caused time loss. This prompted Turán to ask what the minimum number of crossings needed is.
For a full account of this history, see "A Note of Welcome" by Paul Turán.[1]

In 1954, Kazimierz Zarankiewicz published an article named "On a Problem of P. Turán Concerning Graphs."[2] This article contains a proof that cr(Km,n) = ⌊n⁄2⌋⌊n-1⁄2⌋⌊m⁄2⌋⌊m-1⁄2⌋.

Unfortunately, this proof contains an error, as proved by R. K. Guy, in 1969.[3]
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 Kn is 1⁄64(n-1)2(n-3)2, for odd n and 1⁄64n(n-4)(n-2)2 for even n. Guy only proved that this was an upper bound for cr(Kn).

Nonetheless, Zarankiewicz gave a construction for a drawing of Km,n with exactly ⌊n⁄2⌋⌊n-1⁄2⌋⌊m⁄2⌋⌊m-1⁄2⌋ crossings:
If m is even, say m=2k, place these points on the x-axis, with y-coordinates -k,-k-1,...-2,-1,1,2,...k-1,k.
If m is edd, say m=2k+1, place these points on the x-axis, with y-coordinates -k,-k-1,...-2,-1,1,2,...k-1,k,k+1.
Place the n other points in a similar fashion on the y-axis.
If we now connect all points on the x-axis with all points on the y-axis, we get a drawing of Km,n with ⌊n⁄2⌋⌊n-1⁄2⌋⌊m⁄2⌋⌊m-1⁄2⌋ crossings.

Results

Since the problem was conjectured various results have been published through the years. This section contains these results.

Verifications

First of all, we list results in which verifications of parts of the conjecture are published.
  1. 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 Km+1,n contains m+1 copies of Km,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(Km+1,n) = ⌊n⁄2⌋⌊n-1⁄2⌋⌊m+1⁄2⌋⌊m⁄2⌋.

  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(K5,n)=4⌊n⁄2⌋⌊n-1⁄2⌋ and that cr(K6,n)=6⌊n⁄2⌋⌊n-1⁄2⌋. That is, the conjecture holds for K5,n and K6,n for all n.

  3. After a long period without results Douglas R. Woodall verified Zarankiewicz conjecture for K7,7 and K7,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, COn, 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 CO3 the orderings 021 and 201 are adjacent because we can get 201 by changing the order of 0 and 2.

Bounds for the crossing number

Now we will consider results in which bounds are given for the crossing number. Of course the upper bound has already been established by Zarankiewicz in his conjecture.
  1. In Kleitman's article, there is a proof that the crossing number of the complete bipartite graph is bounded below by 1⁄5m(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(Km,n) ≥ 0.8⌊n⁄2⌋⌊n-1⁄2⌋⌊m⁄2⌋⌊m-1⁄2⌋ for m=5.

  2. This bound was improved by Nagi H. Nahas in his article "On the crossing number of Km,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⁄5m(m-1)⌊n⁄2⌋⌊n-1⁄2⌋+9.9×10-6m2n2, for large enough m.
    Nahas proofs that in any drawing of Km,n there are certain non optimal drawings of the subgraph K5,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.

  3. 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 Km,n and Kn", 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⌋.

Complexity

There have been two published results concerning the complexity of calculating the crossing number of complete bipartite graphs.
  1. 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 Km,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.

  2. 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.

Other results

We conclude this section with some other results concerning Zarankiewicz's conjecture.
  1. Richter and Thomassen have proved a connection between cr(Km,n) and cr(Kl) 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)⁄(n4) and cr(Kn,n)⁄(n2)2 both have a limit for n to ∞, defined as LC and LB respectively. Then they conclude that LC ≥ 3⁄2LB.

  2. Considering cr(Kn), we can specify that we only always drawing of Kn 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 Kn, cr(Kn) is equal to cr(Kn) only for n ∈ {1,2,3,4,5,6,7,9}. Their article also contains a rectilineair drawing of K8 with 19 crossings, which is one more than cr(K8).
    Considering cr(Km,n) is not very exciting, because Zarankiewicz's construction already gives us a rectilineair drawing of Km,n with ⌊n⁄2⌋⌊n-1⁄2⌋⌊m⁄2⌋⌊m-1⁄2⌋ crossings.

  3. Continuing the work of Harary and Hill, an article was published by Brodsky, Durocher and Gethner in which they proof that cr(K10)=62. This article was published in 2000 in the Electronic Journal of Combinatorics[12].

  4. Finally, there is a result concerning the crossing number of Km,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 Km,n" proves that the toroidal crossing number of Km,n lies between 1⁄15(m2)(n2) and 1⁄6(m-12)(n-12). Where the lower bound only holds for sufficiently large m and n.

References

[1] Turán, P. "A Note of Welcome." J. Graph Theory 1, 7-9, 1977.
[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"; Proof techniques in Graph Theory pp. 63-69, F. Harary, ed., Academic Press, New York (1969).
[4] D. J. Kleitman "The Crossing Number of K5,n"; J. Combin. Th. 9, pp 315-323, 1970.
[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 Km,n", Electron. J. Combin. 10, 2003.
[7] E. De Klerk, J. Maharry, D. V. Pasechnik, R. B. Richter, G. Salazar, "Improved bounds for the crossing numbers of Km,n and Kn", SIAM J. Discrete Math. 20, pp. 189-202, 2006.
[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", Proc. Edinburgh Math. Soc. (Series 2) pp. 333-338, Cambridge University Press (1963).
[12] A. Brodsky, S. Durocher, E. Gethner, "The Rectilinear Crossing Number of Kn is 62", Electron. J. Combin. 8, 2000
[13] R. K. Guy, T. A. Jenkyns, "The Toroidal Crossing Number of Km,n", J. Combin. Theory 6, pp. 235-250, 1969.

References with a * were inaccessible.

About the author

This site is created by: Wouter van Orsouw, I am a math student at Radboud University Nijmegen.
This site is a project for the course Advanced Graph Theory.
Supervision by: Wieb Bosma.

Last update: August 6th 2010.