Zarankiewicz's conjecture for complete bipartite graphs
Let be the complete bipartite graph with part sizes and , and define
Here denotes the minimum number of crossings in a plane drawing of a graph . Zarankiewicz conjecture.
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
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 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
- OpenAI-165-02-The-crossing-number-of-complete-bipartite-graphs.pdfOpen