On Zarankiewicz' conjecture: the crossing number of K(m,n)

Graphs, Hypergraphs, and Computing

06 March 14:00 - 15:00

Bruce Richter - University of Waterloo

The problem of determining the crossing number of K(m,n) dates back at least to the Second World War. The conjectured value of approximately m(m-1)n(n-1)/16 is achievable by a drawing. Two proofs that the conjecture is right were published in the early 1950's, but recognized in the 1960's to have fatal gaps. Kleitman showed in 1970 that the conjecture holds when min{m,n} is at most 6. More recent computer work with a related convex program has verified the conjecture for the pairs (m,n) with m = 7,8 and n = 7,8,9,10 and provided improved lower bounds for the crossing number of K(m,n) and K(n).

This talk takes the convex program approach one step further and shows that, for each m, either the conjecture is correct for m or there is an explicit function f(m) so that a counterexample exists with n at most f(m).
Magnus M. Halldorsson
Reykjavik University
Klas Markström
Umeå University
Andrzej Rucinski
Adam Mickiewicz University
Carsten Thomassen
Technical University of Denmark, DTU


Klas Markström


For practical matters at the Institute, send an e-mail to