Zarankiewicz's Conjecture

Zarankiewicz's conjecture asserts that graph crossing number for a complete bipartite graph  is

(1)

where  is the floor function. The original proof by Zarankiewicz (1954) contained an error, but was subsequently solved in some special cases by Guy (1969). Zarankiewicz (1954) showed that in general, the formula provides an upper bound to the actual number.

The problem addressed by the conjecture is sometimes known as the brick factory problem, since it was described by Turán (1977) as follows: "We worked near Budapest, in a brick factory. There were some kilns where the bricks were made and some open storage yards where the bricks were stored. All the kilns were connected to all the storage yards. The bricks were carried on small wheeled trucks to the storage yards. All we had to do was to put the bricks on the trucks at the kilns, push the trucks to the storage yards, and unload them there. We had a reasonable piece rate for the trucks, and the work itself was not difficult; the trouble was at the crossings. The trucks generally jumped the rails there, and the bricks fell out from them, in short this caused a lot of trouble and loss of time which was precious to all of us. We were all sweating and cursing at such occasions, I too; but nolens volens 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? I realized after several days that the actual situation could have been improved, but the exact solution of the general problem with m kilns and n storage yards seemed to be very difficult. The problem occurred to me again at my first visit to Poland where I met Zarankiewicz."

The conjecture has been shown to be true for all . Woodall (1993) settled the  case, with the smallest unsettled cases as of Feb. 2009 being  and . The table below gives known results.

Richter and Širáň (1996) computed the crossing number of the complete bipartite graph  as

(2)

Kleitman (1970, 1976) showed that the crossing numbers for , , , and  satisfy

(3)

giving the specific equations

			(4)
			(5)
			(6)
			(7)

for all positive .

REFERENCES

de Klerk, E.; Maharry, J.; Pasechnik, D. V.; Richter, R. B.; Salazar, G. "Improved Bounds for the Crossing Numbers of  and ." 2004

 https://arxiv.org/pdf/math/0404142.pdf.Guy, R. K. "The Decline and Fall of Zarankiewicz's Theorem." In Proof Techniques in Graph Theory, Proceedings of the Second Ann Arbor Graph Theory Conference, Ann Arbor, Michigan, 1968. New York: Academic Press, pp. 63-69, 1969.

Kővari, T.; Sós, V. T.; and Turán, P. "On a Problem of K. Zarankiewicz." Colloq. Math. 3, 50-57, 1954.

Kleitman, D. J. "The Crossing Number of ." J. Combin. Th. 9, 315-323, 1970.

Richter, R. B. and Širáň, J. "The Crossing Number of  in a Surface." J. Graph Th. 21, 51-54, 1996.

Richter, R. B. and Thomassen, C. "Relations Between Crossing Numbers of Complete and Complete Bipartite Graphs." Amer. Math. Monthly 104, 131-137, 1997.

Turán, P. "A Note of Welcome." J. Graph Th. 1, 7-9, 1977.Woodall, D. R. "Cyclic-Order Graphs and Zarankiewicz's Crossing-Number Conjecture." J. Graph Th. 16, 657-691, 1993.

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