Zarankiewicz crossing number conjecture

Turán brick factory problem

P. Turán [a6] tells about how he posed the following problem while in a forced labour camp in World War II: "There were some kilns where the bricks were made and some open storage yards where the bricks were stored. All the kilns were connected by rail with all storage yards. … the trouble was only at crossings. The trucks generally jumped the rails there, and the bricks fell out of them; in short this caused a lot of trouble and loss of time … the idea occurred to me that this loss of time could have been minimized if the number of crossings of the rails had been minimized. But what is the minimum number of crossings?"

Recall that a drawing of a finite graph $G$ on the plane consists of placing the vertices of $G$ on the plane and drawing the edges of $G$ using continuous curves of the plane, connecting corresponding vertices as endpoints of the curve such that no curve has a vertex as an internal point and no point is an internal point of $3$ curves. The crossing number $\text{cr} ( G )$ of a graph $G$ is the minimum number of intersection points among the curves representing edges, over all possible drawings of the graph. It is not hard to see that the crossing number can always be realized by a drawing with the following properties:

i) there is no self-crossing of edges;

ii) edges with the same endpoint do not cross;

iii) intersection points among the curves representing edges are crossing points, i.e. the curves do not touch each other; and

iv) any two edges intersect at most once. For variations in the definition of crossing numbers, see [a1].

Put in the technical terms above, Zarankiewicz' crossing number conjecture, or Turán's brick factory problem, is as follows: "what is the crossing number crKn,m of the complete bipartite graph Kn,m?"

Place $\lfloor n / 2 \rfloor$ vertices to negative positions on the $x$-axis, $\lceil n / 2 \rceil $ vertices to positive positions on the $x$-axis, $\lfloor m/ 2 \rfloor$ vertices to negative positions on the $y$-axis, $[ m / 2 ]$ vertices to positive positions on the $y$-axis, and draw edges by straight line segments to obtain a drawing of $K _ { n , m}$. It is not hard to check that the following formula gives the number of crossings in this particular drawing:

\begin{equation} \tag{a1} \left\lfloor \frac { n } { 2 } \right\rfloor \left\lfloor \frac { n - 1 } { 2 } \right\rfloor \left\lfloor \frac { m } { 2 } \right\rfloor \left\lfloor \frac { m - 1 } { 2 } \right\rfloor. \end{equation}

K. Zarankiewicz [a10] and K. Urbaník [a7] independently claimed and published that $\operatorname { cr } ( K _ { n , m} )$ was actually equal to (a1), their argument was reprinted in a book, cited, and used in follow-up papers. However, P. Kainen and G. Ringel discovered a flaw in the argument and the flaw has withstood all attempts for correction (up till 2000). R. Guy deserves much credit for rectifying this confused state of art, see [a2] and [a3].

D.J. Kleitman showed that (a1) holds for $m \leq 6$ [a4] and also proved that the smallest counterexample to the Zarankiewicz conjecture must occur for odd $n$ and $m$. D.R. Woodall [a9] used an elaborate computer search to show that (a1) holds for $K _ { 7 , 7}$ and $K _ { 7 , 9}$. Thus, the smallest unsettled instances of Zarankiewicz's conjecture are $K _ { 7 , 11}$ and $K _ { 9 , 9}$. It is known that

\begin{equation*} c = \operatorname { lim } _ { n \rightarrow \infty } \operatorname { cr } ( K _ { n , n } ) \left( \begin{array} { l } { n } \\ { 2 } \end{array} \right) ^ { - 2 } \end{equation*}

exists; however, the value of the limit is not known (as of 2000) [a5]. Woodall's result for $K _ { 7 , 9}$ implies $4 / 21 \leq c$ by a standard counting argument, while $c \leq 1 / 4$ follows from the drawing shown. If (a1) always holds, then $c = 1 / 4$.

References

[a1]	J. Pach, G. Tóth, "Which crossing number is it anyway?" , Proc. 39th Ann. Symp. Foundation of Computer Sci. , IEEE Press (1998) pp. 617–626
[a2]	R.K. Guy, "The decline and fall of Zarankiewicz's theorem" F. Harary (ed.) , Proof Techniques in Graph Theory , Acad. Press (1969) pp. 63–69
[a3]	R.K. Guy, "# 21749" Math. Rev. , 58 (1974)
[a4]	D.J. Kleitman, "The crossing number of $K _ { 5 ,\, n }$" J. Combin. Th. , 9 (1970) pp. 315–323
[a5]	R.B. Richter, C. Thomassen, "Relations between crossing numbers of complete and complete bipartite graphs" Amer. Math. Monthly , 104 (1997) pp. 131–137
[a6]	P. Turán, "A note of welcome" J. Graph Th. , 1 (1977) pp. 7–9
[a7]	K. Urbaník, "Solution du problème posé par P. Turán" Colloq. Math. , 3 (1955) pp. 200–201
[a8]	A.T. White, L.W. Beineke, "Topological graph theory" L.W. Beineke (ed.) R.J. Wilson (ed.) , Selected Topics in Graph Theory , Acad. Press (1978) pp. 15–50
[a9]	D.R. Woodall, "Cyclic-order graphs and Zarankiewicz's crossing-number conjecture" J. Graph Th. , 17 (1993) pp. 657–671
[a10]	K. Zarankiewicz, "On a problem of P. Turán concerning graphs" Fundam. Math. , 41 (1954) pp. 137–145