Turan's Brickyard Problem: The Crossing Number of the Complete Bipartite Graph

A drawing of a graph is a depiction in the plane so that nonadjacent edges are allowed to cross at most once transversally. The crossing number of a graph G, cr(G), is the minimum number of pairwise transversal crossings over all drawings of G. Let K_{n,m} denote the complete bipartite graph on n+m vertices.

Conjecture: cr(K_{n,m}) = [n/2] [(n-1)/2] [m/2] [(m-1)/2] where [x] denotes the integer part of x.

This problem is historically known as Turan's Brickyard Problem. The vertices in one partite set are the kilns in a brickyard; the vertices in the other partite set are the shipping depots. Each kiln is to be connected by a train track to each depot. However, when tracks cross the cars are likely to be derailed. Hence it is useful to find the layout of kilns, depots, and tracks that minimizes the number of crossings.

The conjectured bound can be realized by the following drawing. Placing n/2 vertices along both the positive and negative x-axis (or (n+1)/2 and (n-1)/2 respectively if n is odd), and m/2 vertices along the positive and negative y-axis (again, splitting nearly equally if m is odd). Now connect each pair of vertices on different axes with straight line segments. The difficulty is showing that every drawing has at least this many crossings.

The problem was thought to have been solved by Zarankiewicz, but the flaw in his proof was detailed by Guy [G]. Assuming that n is at most m, the bound is exact for n at most 6 and for n=7 and m at most 10. Maybe the most interesting small open case is to find the crossing number of  K_{9,9}. It is tempting to study the problem combinatorially (see A Combinatorial Generalization of Drawing the Complete Graph'' in this collection of problems), but the situation is complicated by the fact that the local rotations on K_{3,3} do not determine exactly the number of crossings in that induced drawing.

A recent result by Nahas [N] shows that cr(K_{n,m}) >= 1/5 m(m-1)(\floor(n/2))( \floor((n-1)/2))) + 9.9 \times 10^(-6) m^2n^2 for sufficently large m and n.

An even more recent result [KPRS] shows that the crossing number is at least .83 times its conjectured value.

References:

[G] R. Guy, The decline and fall of Zarankiewicz's theorem, in Proof Techniques in Graph Theory (F. Harary Ed.), Academic Press, New York (1969) 63-69.

[K] D. Kleitman, The crossing number of K_{5,n}, J. Combin. Theory 9 (1970) 315-323.

[KPRS] E. de Klerk, D. Pasechnik, R.B. Richter, and G. Salazar, personal communication.

[N]  N. Nahas, On the crossing number of K_{n,m}, Electronic Journal of Combinatorics, 10(1) (2003)

[W] D.R. Woodall, Cyclic-order graphs and Zarankiewicz's crossingg-number conjecture, preprint

Submitted by: Dan Archdeacon, Department of Mathematics and Statistics, University of Vermont, Burlington VT 05405 USA

Send comments to dan.archdeacon@uvm.edu

August, 1995, updated November, 2003.