The Crossing Number of the Complete Bipartite Graph
OPG_crossing_number_complete_bipartite_zarankiewicz
Source: Open Problem Garden: the_crossing_number_of_the_complete_bipartite_graph
Status ai-proved high confidence
OpenAI's manuscript proves Zarankiewicz's formula $\mathrm{cr}(K_{m,n}) = \lfloor\frac m2\rfloor\lfloor\frac{m-1}2\rfloor\lfloor\frac n2\rfloor\lfloor\frac{n-1}2\rfloor$ for all positive $m, n$, settling Turán's brick factory problem.
Cited literature (2)
-
Establishes new lower bounds cr(K_{10,n}) >= 4.87057 n^2 - 10n, cr(K_{11,n}) >= 5.99939 n^2 - 12.5n, cr(K_{12,n}) >= 7.25579 n^2 - 15n, cr(K_{13,n}) >= 8.65675 n^2 - 18n via semidefinite programming with full symmetry exploitation.
-
partial Improved lower bounds for the 2-page crossing numbers of $K_{m,n}$ and $K_n$ via semidefinite programming (2012)
Shows that the Zarankiewicz conjecture holds asymptotically for the 2-page crossing number variant with m=7 and m=8 (i.e., lim_{n->inf} cr_2(K_{m,n})/Z(m,n) = 1), and improves bounds for the 2-page crossing number of K_n.
Reviewer notes. Literature status before this model-generated claim: partial. The Zarankiewicz conjecture that $\mathrm{cr}(K_{m,n}) = \lfloor m/2 \rfloor \lfloor (m-1)/2 \rfloor \lfloor n/2 \rfloor \lfloor (n-1)/2 \rfloor$ remains open in general; it has been verified for $\min\{m,n\} \le 6$ and a handful of small cases (up to $K_{8,10}$), with the best published asymptotic lower bound at $0.83\,Z(m,n)$ for fixed $m \ge 9$. Since the 2007 posting, Brosch and Polak (2023) have used semidefinite programming to establish new explicit lower bounds for $K_{m,n}$ with $m \in \{10,11,12,13\}$, extending the reach of SDP methods beyond what de Klerk et al. (2006) had achieved.
OpenAI manuscript collection ai-proved
- The crossing number of complete bipartite graphs — main result formalized in Lean by OpenAI
Family 165: The Harary–Hill and Zarankiewicz crossing-number formulas · Lean formalization scope
These manuscripts were produced by an unreleased OpenAI model and released on
2026-10-06 in github.com/openai/math.
They have not been peer reviewed. Lean formalizations are OpenAI's own and cover
only the scope stated on their scope page; this project has not run or reviewed them.
The status above records the claim; before it, the literature review rated this
entry partial. Its confidence rates
whether the manuscript's theorem settles this entry, not whether the manuscript
is correct.
Discussion
(This discussion appears as [M].) A drawing of a graph $ G $ in the plane has the vertices represented by distinct points and the edges represented by polygonal lines joining their endpoints such that: \item no edge contains a vertex other than its endpoints, \item no two adjacent edges share a point other than their common endpoint, \item two nonadjacent edges share at most one point at which they cross transversally, and \item no three edges cross at the same point. This problem is also known as Turan's Brickyard Problem (since it was formulated by Turan when he was working at a brickyard - the edges of the drawing would correspond to train tracks connecting different shipping depots, and fewer crossings would mean smaller chance for collision of little trains and smaller chance for their derailing). This conjectured value for the crossing number of $ K_{m,n} $ can be realized by the following drawing. Place $ \ceil{n/2} $ vertices on the positive $ x $ -axis and $ \floor{n/2} $ vertices on the negative $ x $ -axis. Similarly, place $ \ceil{m/2} $ and $ \floor{m/2} $ along the positive and negative $ y $ -axis. Now connect each pair of vertices on different axes with straight line segments.
Bibliography
-
[G]R. Guy, The decline and fall of Zarankiewicz's theorem, in Proof Techniques in Graph Theory (F. Harary Ed.), Academic Press, New York (1969) 63-69. -
[K]D. Kleitman, The crossing number of K_{5,n} , J. Combin. Theory 9 (1970) 315-32 -
[M]B. Mohar, Problem of the Month Problem of the Month