Zarankiewicz's conjecture for complete bipartite graphs

From papers

Let Km,nK_{m,n} be the complete bipartite graph with part sizes mm and nn, and define

Z(m,n):=n2n12m2m12.Z(m,n):=\left\lfloor\frac{n}{2}\right\rfloor\left\lfloor\frac{n-1}{2}\right\rfloor\left\lfloor\frac{m}{2}\right\rfloor\left\lfloor\frac{m-1}{2}\right\rfloor.

Here cr(G)\operatorname{cr}(G) denotes the minimum number of crossings in a plane drawing of a graph GG. Zarankiewicz conjecture.

cr(Km,n)=Z(m,n).\operatorname{cr}(K_{m,n})=Z(m,n).

Zarankiewicz constructed a drawing attaining this number, but a flaw was found in his claimed proof of optimality. The conjecture remains open in general.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Ruy Fabila-Monroy, Rosna Paul, Jenifer Viafara-Chanchi and Alexandra Weinberger, “On the rectilinear crossing number of complete balanced multipartite graphs and layered graphs”, arXiv:2404.13155 (2025).

Solutions 0

No solutions have been posted yet.