Zarankiewicz’s complete-bipartite crossing-number formula
Follow the latest progress by email.
Does the ordinary crossing number of Kₘ,ₙ equal ⌊m/2⌋⌊(m−1)/2⌋⌊n/2⌋⌊(n−1)/2⌋ for all positive m,n? Drawings use continuous simple edge paths in the plane.
Why it matters and what counts as progress
Why it matters: The formula would prove optimality of the classical complete-bipartite drawing beyond the known small-part cases.
What counts as progress: A matching lower bound for all part sizes, a new proved range, or a drawing beating the formula, with the ordinary drawing convention retained.
How the problem developed
AI contribution
The crossing number of complete bipartite graphs
For all positive integers m and n, the ordinary crossing number of the complete bipartite graph Kₘ,ₙ equals ⌊m/2⌋⌊(m−1)/2⌋⌊n/2⌋⌊(n−1)/2⌋ for plane drawings with continuous simple edge paths.
Sources
Website timeline
Publication dates and editorial changes.