Zarankiewicz's conjecture for complete bipartite graphs

About 2 years old · traced to

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

Z(m,n):=⌊n2⌋⌊n−12⌋⌊m2⌋⌊m−12⌋.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.

References

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).

Progress summary

Never refreshed

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

Solutions 1

RemarkAI-assistedClaimed by OpenAI.See full solutionHide full solution

Claimed by OpenAI.

Claims the ordinary crossing number of K_(m,n) equals floor(m/2) floor((m-1)/2) floor(n/2) floor((n-1)/2) for all positive integers m,n, with unrestricted vertex positions and edge routes.

Repository: https://github.com/openai/math

Manuscript: https://github.com/openai/math/blob/adc7f1241b42e322a6451854ab7e4b4c146bf78a/preprints/The-crossing-number-of-complete-bipartite-graphs-September-23-2026/paper.pdf

  • OpenAI-165-02-The-crossing-number-of-complete-bipartite-graphs.pdf406,173 bytesOpen