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 kilns and storage yards seemed to be very difficult. The problem occurred to me again at my first visit to Poland where I met Zarankiewicz. I mentioned to him my 'brick-factory' problem and Zarankiewicz thought he had solved it. But Gerhard Ringel found a gap in his published proof, which nobody has been able to fill so far--in spite of much effort. This problem has also become a notoriously difficult unsolved problem."

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 .