Progress checking Zarankiewicz’s conjecture on the brick factory problem

By David Orden October 1, 2013 1 comment Print

A previous post presented the fascinating history of the brick factory problem, which wonders about the smallest possible number of rail crossings when connecting $m$ kilns and $n$ storage yards¹, which is mathematically modeled by the crossing number of the complete bipartite graph $K_{m,n}$ .

Proposed by Paul Turán after the Second World War, the first advances on this problem arose in 1952, due to the probabilist Kazimierz Urbanik and the topologist Kazimierz Zarankiewicz. The latter claimed to have solved the problem, stating that the smallest possible number of crossings $cr(K_{m,n})$ was $\lfloor m/2\rfloor \cdot \lfloor (m-1)/2\rfloor \cdot \lfloor n/2\rfloor \cdot \lfloor (n-1)/2\rfloor$ and proposing a simple way of attaining this number.

It would be enough to (1) draw the $m$ vertices on the x-axis, split as evenly as possible among the strictly positive and the strictly negative semi-axes, (2) proceed analogously with the $n$ vertices on the y-axis, and (3) use straight-line segments to join pairs of vertices lying on different axes.

Unfortunately, the proof was found to be incorrect around 1965 ² and, more than sixty years later, Zarankiewicz’s conjecture remains one of the most tantalizing open problems in graph theory.

During these years, some advances have been achieved checking the conjecture for a few values. Zarankiewicz’s proof³, published in 1952, did work for the case $m=3$ . A paper by Kleitman⁴, in 1970, extended the validity to $m\leq 6$ and Woodall⁵, in 1993, checked the cases $m\in\{7,8\}$ and $n\in\{7,8,9,10\}$ with the help of computers.

The aim of this post is to introduce a different kind of progress on checking Zarankiewicz’s conjecture, presented by Christian et al. ⁶ in a recent paper. For each fixed $m$ , the authors manage to determine an integer $N_0$ (depending on $m$ ) such that:

If Zarankiewicz’s conjecture holds for the fixed $m$ together with all $n\leq N_0$ ,

then it holds for that $m$ together with every $n$ .

In other words, what this paper shows is that, for a given $m$ , checking Zarankiewicz’s conjecture reduces to checking a finite number of values for $n$ (which is in turn a finite problem). But do not start shouting about it. It turns out that the method is not practical even for $m=5$ .

The expression of $N_0$ obtained by the authors is

$N_0(m)=((2\cdot Z(m))^{m!}(m!)!)^4$ ,

where $Z(m)=\lfloor m/2\rfloor \cdot \lfloor (m-1)/2\rfloor$ (note that this is the part using $m$ in the expression for Zarankiewicz’s conjecture).

This means that $N_0(5) \approx 6\cdot 10^{1228}$ , a really big number. The fastest computers today perform in the order of petaFLOPS ( $10^{15}$ operations per second), so even if they could check each case in a single operation, it would take in the order of $10^{1204}$ years to check if the conjecture holds for $K_{5,n}$ with all $n\leq N_0$ .

Nevertheless, the result is a remarkable progress in such a tantalizing problem. Although giving full details about the proofs is certainly out of the scope of this post, we can outline the arguments used by Christian et al. In order to do so, we just need to introduce two notions about drawings of $K_{m,n}$ .

Consider the vertices in the two classes of the bipartite graph (white and black points in the previous figure) labeled as $[m]=\{1,\ldots,m\}$ and $[n]=\{1,\ldots,n\}$ . Before introducing the first notion observe that, in any drawing, each vertex $v$ of the second class induces a natural cyclic order of $[m]$ , just considering the clockwise cyclic order of the edges incident to it. This cyclic order is the rotation of the vertex in the drawing. The following figure shows a rotation $1,2,4,3,5$ .

Note that there are $(m-1)!$ possible rotations for a vertex of degree $m$ , since this is the number of cyclic permutations of $[m]$ .

The second notion is what Christian et al. call templates. A drawing of $K_{m,k}$ is defined to be a template of rank $m$ and order $k$ if there are no two vertices of degree $m$ having the same rotation. The authors show that, for each positive integer $n$ , there is an optimal drawing of $K_{m,n}$ that can be obtained (1) from some template of rank $m$ and order $k$ (2) by duplicating vertices of degree $m$ in the template, and (3) so that the crossing number of the resulting optimal drawing of $K_{m,n}$ can be determined by information contained in the template and the distribution of the duplicate vertices.

A key fact is that, up to isomorphism, the number of templates to consider turns out to be finite.

Then, the authors associate a quadratic program to each template, in such a way that the minimum of the quadratic program provides information about whether, for this template, a drawing of $K_{m,n}$ obtained as above is a counterexample to Zarankiewicz’s conjecture.

In summary, although not being practical today, the paper by Christian et al. opens a way towards checking Zarankiewicz’s conjecture for a given value of $m$ . Furthermore, it remarkably finds its place in the list of very few results around this conjecture in the last sixty years.

References

Lowell Beineke and Robin Wilson. The Early History of the Brick Factory Problem. The Mathematical Intelligencer. Volume 32, Issue 2 (June 2010), pages 41-48. http://dx.doi.org/10.1007/s00283-009-9120-4. ↩
Richard K. Guy. The decline and fall of Zarankiewicz’s theorem. In: Proof Techniques in Graph Theory (ed. F. Harary), New York: Academic Press (1969), pages 63–69. ↩
K. Zarankiewicz. On a problem of P. Turan concerning graphs. Fundamenta Mathematicae. Volume 41 (1954), pages 137–145. ↩
Daniel J. Kleitman. The crossing number of $K_{5,n}$ . Journal of Combinatorial Theory. Volume 9 (1970), pages 315–323. http://dx.doi.org/10.1016/S0021-9800(70)80087-4 ↩
Douglas R. Woodall, Cyclic-order graphs and Zarankiewicz’s crossing-number conjecture, Journal of Graph Theory. Volume 17, Issue 6 (December 1993), pages 657–671. http://dx.doi.org/10.1002/jgt.3190170602 ↩
Christian R., Richter R.B. & Salazar G. (2013). Zarankiewiczʼs Conjecture is finite for each fixed m, Journal of Combinatorial Theory, Series B, 103 (2) 237-247. DOI: 10.1016/j.jctb.2012.11.001 ↩

1 comment

El problema matemático que nació en un campo de trabajo de la Segunda Guerra Mundial | Cifras y Teclas

February 26, 2014

[…] escribí para Mapping Ignorance y que llegó hasta reddit. En el mismo blog, en la entrada Progress checking Zarankiewicz’s conjecture on the brick factory problem, puedes encontrar algunos progresos recientes relacionados con este problema. Aunque no han […]

References

1 comment

Leave a ReplyCancel reply

Leave a Reply