Conjecture about minimal number of edge crossings in complete bipartite graphs

Question

I am interested in the status of the conjecture about the minimum number of edge crossings $cr(K_{m,n})$ in a drawing of the complete bipartite graph $K_{m,n}$.

The Wikipedia article https://en.wikipedia.org/wiki/Tur%C3%A1n%27s_brick_factory_problem led me to study the original papers of Zarankiewicz (On a problem of P. Turan concerning graphs) from 1954 and of Urbanik (Solution du problème posé par P. Turán) from 1955.

I wondered whether someone could tell me whether an asymptotic approach has been successfully attempted (letting $n\to\infty$). If so, I would be very interested in any references for that.

Answer 1

The Electronic Journal of Combinatorics has many Dynamic Surveys one of which is The Graph Crossing Number and its Variants: A Survey by Schaefer which first appeared in 2013 and has been updated as recently as Feb 14, 2020. From the bottom of page 40 onto page 41 you will find this conjecture for complete bipartite graphs discussed (with many references). As far as I can tell from the survey the conjecture is open (both for exact values and asymptotically).

One paper you might be interested in is Zarankiewiczʼs Conjecture is finite for each fixed $m$ by Christiana, Richter, and Salazar. This paper shows that for each $m$ if the conjecture holds up for all $n$ up to some very large $N(m)$ (which is an explicit value), then the conjecture is true for $K_{n,m}$ with any $n$.

This survey also references another survey Turán’s Brick Factory Problem: The Status of the Conjectures of Zarankiewicz and Hill by Székely. (I haven't be able to access this survey so I don't exactly what's inside.)

Answer 2

It is a fascinating conjecture. The following might be a good reference for you: In 1997, Richter & Thomassen showed that $$\lim_{n\to\infty}cr(K_{n,n})\left(\begin{array}{c} n \\ 2 \end{array}\right)^{-2}$$ exists and is at most $1/4$. If the conjecture is true, the value of this limit is exactly $1/4$. (R.B. Richter, C. Thomassen, "Relations between crossing numbers of complete and complete bipartite graphs" Amer. Math. Monthly , 104 (1997) pp. 131–137)

As of 2017, the exact value of this limit is still not known, see for example Gethner, Hogben, Lidick, Pfender, Ruiz, Young: „Crossing numbers of complete tripartite and balanced complete multipartite graphs“" Journal of Graph Theory 84, no. 4 (2017): 552-565. DOI: 10.1002/jgt.22041