**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,

Send comments to *dan.archdeacon@uvm.edu
*

August, 1995, updated November, 2003.