Turán's brick factory problem

The problem is named after Pál Turán, who formulated it while being forced to work in a brick factory during World War II.

Turán was inspired by this situation to ask how the factory might be redesigned to minimize the number of crossings between these tracks.

Similarly, place n vertices on the y-axis of the plane, avoiding the origin, with equal or nearly-equal numbers of points above and below the x-axis.

The gap was not discovered until eleven years after publication, nearly simultaneously by Gerhard Ringel and Paul Kainen.

[2] Since Km,n and Kn,m are isomorphic, it is enough to consider the case where m ≤ n. In addition, for m ≤ 2 Zarankiewicz's construction gives no crossings, which of course cannot be bested.

It has since been extended to other small values of m, and the Zarankiewicz conjecture is known to be true for the complete bipartite graphs Km,n with m ≤ 6.

However, the upper bound established by Zarankiewicz for the crossing numbers of complete bipartite graphs can be achieved using only straight edges.