Turán's brick factory problem was devised in 1944 by Hungarian mathematician Pál Turán.

As a WW2 prisoner, Turán had been forced to work in a Transylvanian brick factory, where his job was to move bricks, using hand-pushed rail-carts, from various kilns to various storage yards. All the kilns were connected by rail with all the storage yards. The tracks inevitably (and inconveniently) crossed, leading Turán to wonder “What is the minimum number of crossings?”

Turán's colleague, mathematician Kazimierz Zarankiewicz, found a way of solving the problem with a drawing method (diag.), and a mathematical 'proof' - but the 'proof' was later found to contain errors. This led to the Zarankiewicz crossing number conjecture - which asks :

Can any complete bipartite graph be drawn with fewer crossings than the number given by Zarankiewicz?

More formally : It is always possible to draw the complete bipartite graph K_m,n (a graph with m vertices on one side, n vertices on the other side, and mn edges connecting the two sides) with a number of crossings equal to :

$$ {\displaystyle \operatorname {cr} (K_{m,n})\leq {\biggl \lfloor }{\frac {n}{2}}{\biggr \rfloor }{\biggl \lfloor }{\frac {n-1}{2}}{\biggr \rfloor }{\biggl \lfloor }{\frac {m}{2}}{\biggr \rfloor }{\biggl \lfloor }{\frac {m-1}{2}}{\biggr \rfloor }.} $$

But is this always the minimum?

Although it's now been solved for some special cases, the general problem remains unsolved.

Further reading : Wolfram Mathworld

---

Please share this page to help promote Wikenigma !