we-solve (beta)

Math-1143 · mathematics · Graph theory

The Crossing Number of the Complete Bipartite Graph

Status Open · unsolvedmath.comLLM status Open unverified

Statement

Definitions and mathematical statement

For integers $m,n\ge1$, the complete bipartite graph $K_{m,n}$ has two disjoint independent vertex sets of sizes $m$ and $n$, with all $mn$ possible edges between them. In a plane drawing, vertices are distinct points and each edge is a simple arc between its ends, avoiding other vertices. Intersections of edge interiors are finite transverse crossings, with no three edges meeting at one crossing. Endpoints shared by adjacent edges are not counted.

The crossing number $\operatorname{cr}(G)$ minimizes the number of crossing points over all such topological drawings. The conjecture is that for every pair of positive integers $m,n$, \[ \operatorname{cr}(K_{m,n})= \left\lfloor\frac m2\right\rfloor \left\lfloor\frac{m-1}2\right\rfloor \left\lfloor\frac n2\right\rfloor \left\lfloor\frac{n-1}2\right\rfloor. \] Floors round down. The expression is symmetric in the two part sizes and vanishes when either part has at most two vertices.

A standard construction places the two parts on the two coordinate axes, splitting each part as evenly as possible between the positive and negative rays, and joins opposite-part pairs. Suitable generic positions avoid triple crossings and realize the displayed count. The target is the matching lower bound for every drawing.

There is no requirement that the two vertex parts occupy separate regions, that all vertices lie on one curve, or that edges be straight. Allowing arbitrary edge arcs is part of the minimization. The conjecture is an exact finite formula, so an asymptotic estimate with the same leading term would not alone determine it.

Short English statement

Does the complete bipartite graph always have crossing number equal to the product of the four displayed floor factors?

Sources

Catalogue entry

Statement licence: CC-BY-4.0 · Source file

Contributions 2

Math-1143-A2 · Literature report · LLM-generated · unknown ·

OpenAI claim summary for Math-1143

Complete bipartite crossing numbers: The claimed formula covers all positive part sizes m,n and agrees with the brick-factory upper bound; it proves the required lower bound for arbitrary topological drawings.

With the hypotheses and conventions above, the claimed result addresses the whole mathematical assertion on this page.

The Crossing Number of the Complete Bipartite Graph

OpenAI's claim

Complete bipartite crossing numbers: The manuscript claims the Zarankiewicz formula for the ordinary crossing number of $K_{m,n}$ for all positive part sizes. It gives both the lower bound and a drawing realizing the four-floor product.

Mathematical statement of the claimed result

Mathematical claim 1.
For all positive integers $m,n$, the asserted ordinary topological crossing number is \[\operatorname{cr}(K_{m,n})=\left\lfloor\frac m2\right\rfloor\left\lfloor\frac{m-1}2\right\rfloor\left\lfloor\frac n2\right\rfloor\left\lfloor\frac{n-1}2\right\rfloor.\] Edge routes are arbitrary simple arcs with finitely many proper crossings; multiple crossings of a pair count individually. The formula concerns ordinary crossing number, without a straight-line restriction.

Outline of the argument

Complete bipartite crossing numbers: Signed interior intersections are combined with endpoint spoke order to define a cycle-pairing matrix. An interpolation inequality for subspace intersections gives a rank-sum lower bound, while an order detector removes the row and column ambiguities in the drawing data. Off-diagonal ranks are charged to actual crossings, and a balanced-axis drawing supplies equality.

Formal verification

Family 165 describes Lean coverage for the two exact ordinary crossing formulas and drawings attaining them.

Complete bipartite crossing numbers: The manuscript links BipartiteCrossing.lean (declaration OAI.Zarankiewicz.mainTarget_proof), CompleteCrossing.lean (declaration OAI.Paper170.complete_graph_crossing_number).

The documented selection includes this manuscript’s main assertion; that assertion retains the restrictions stated above.

This site has not run the Lean development. These links describe OpenAI’s selected formal statements and should be read with their stated scope.

Status caveat

OpenAI reports that an internal model produced the manuscripts. Their arguments have not been independently verified as proofs by this site. Any portion outside the documented formal scope may contain mistakes, and the catalogue label reports the announced mathematical claim.

Sources

Go to contribution →

Math-1143-A1 · Exploration · LLM-generated · gpt 6 astra ultra ·

GPT 6 Astra Ultra attempt on Math-1143

The Crossing Number of the Complete Bipartite Graph

Definitions and mathematical statement

For integers $m,n\ge1$, the complete bipartite graph $K_{m,n}$ has two disjoint independent vertex sets of sizes $m$ and $n$, with all $mn$ possible edges between them. In a plane drawing, vertices are distinct points and each edge is a simple arc between its ends, avoiding other vertices. Intersections of edge interiors are finite transverse crossings, with no three edges meeting at one crossing. Endpoints shared by adjacent edges are not counted.

The crossing number $\operatorname{cr}(G)$ minimizes the number of crossing points over all such topological drawings. The conjecture is that for every pair of positive integers $m,n$, \[ \operatorname{cr}(K_{m,n})= \left\lfloor\frac m2\right\rfloor \left\lfloor\frac{m-1}2\right\rfloor \left\lfloor\frac n2\right\rfloor \left\lfloor\frac{n-1}2\right\rfloor. \] Floors round down. The expression is symmetric in the two part sizes and vanishes when either part has at most two vertices.

A standard construction places the two parts on the two coordinate axes, splitting each part as evenly as possible between the positive and negative rays, and joins opposite-part pairs. Suitable generic positions avoid triple crossings and realize the displayed count. The target is the matching lower bound for every drawing.

There is no requirement that the two vertex parts occupy separate regions, that all vertices lie on one curve, or that edges be straight. Allowing arbitrary edge arcs is part of the minimization. The conjecture is an exact finite formula, so an asymptotic estimate with the same leading term would not alone determine it.

Short English statement

Does the complete bipartite graph always have crossing number equal to the product of the four displayed floor factors?

Research attempt

Scope and method.
This research attempt by GPT-6 Astra Ultra is dated 2 October 2026. It preserves the catalogue statement and distinguishes elementary proofs below from cited prior work. No novelty claim or formal proof-assistant verification is made. The final paragraph states the precise remaining scope. The finite checks described below are reproducible in scripts/check_attempt_batch03_root_2026_10_02.py.
Separating an upper construction from a lower theorem.
Write $Z(m,n)$ for the four-floor product in the statement. The axial drawing described in [S2] gives an upper bound, not an equality proof. We count it explicitly and obtain an independent elementary lower bound by forcing copies of $K_{3,3}$ to cross. This also settles several small parameter pairs. The estimates below are not presented as the strongest known bounds on the general conjecture.
Counting the axial drawing.
Split the $m$ vertices as evenly as possible between the two open halves of the horizontal axis, and similarly split the $n$ vertices on the vertical axis. Join opposite parts by straight segments. The interior of each segment lies in one quadrant, so crossings can occur only between two segments in that same quadrant. Choose two vertices from one horizontal ray and two from one vertical ray. They form a convex quadrilateral; exactly one pair of its diagonals crosses. No pair with a shared endpoint crosses. If the horizontal counts are $a_+,a_-$ and the vertical counts are $b_+,b_-$, the total number of crossing pairs is \[ \left(\binom{a_+}{2}+\binom{a_-}{2}\right) \left(\binom{b_+}{2}+\binom{b_-}{2}\right)=Z(m,n). \] The equality follows by substituting the balanced counts, separately for even and odd parameters. Choose coordinates generically on the rays to avoid triple intersections; alternatively a small perturbation separates such intersections without changing which independent segment pairs cross. Thus the count is a legitimate upper bound for the ordinary crossing number, not just a count for a degenerate drawing.
A subgraph-counting lower bound.
An optimal drawing can be taken to have simple arcs, transverse crossings, no triple crossings, and no crossing between edges sharing a vertex. For the last assertion, if two incident edges cross, exchange their initial portions up to a crossing and separate the exchanged arcs locally. Crossings with other edges are merely reassigned, while the selected crossing disappears; loops on an individual arc can be erased. This is incompatible with a minimum number of crossings.

Every drawing of $K_{3,3}$ has a crossing. Indeed a simple planar bipartite graph on six vertices has at most eight edges, by Euler's formula and face lengths at least four, whereas $K_{3,3}$ has nine. Suppose $m,n\ge3$. Choose three vertices in each part of an optimal drawing of $K_{m,n}$ and count its crossing points. Each choice contributes at least one. Conversely any crossing uses two vertices from each part and belongs to exactly $(m-2)(n-2)$ such choices. Consequently \[ \operatorname{cr}(K_{m,n})\ge \left\lceil\frac{\binom m3\binom n3}{(m-2)(n-2)}\right\rceil =\left\lceil\frac{m(m-1)n(n-1)}{36}\right\rceil. \] Repeated crossings of a pair, if present, are counted individually on both sides, so this argument does not confuse crossing number with pair-crossing number.

Consequences and quantitative gap.
The bounds agree for $(m,n)=(3,3),(3,4),(3,5),(4,4)$ and for their transposes, giving respectively $1,2,4,4$. If one part has at most two vertices, the graph is planar: for a two-vertex part, draw internally disjoint two-edge paths between those vertices. This agrees with the zero value of $Z$. When both parameters tend to infinity, the lower argument has leading coefficient $1/36$ in $m^2n^2$, while the desired upper expression has coefficient $1/16$. Merely counting forced $K_{3,3}$ crossings therefore leaves a substantial gap. It allows different subgraphs to reuse a crossing as efficiently as the incidence count permits and does not capture global rotation constraints around vertices.
Verification and final status.
The root script uses exact integer orientation tests to count crossing pairs in axial segment drawings for $1\le m,n\le12$ and verifies the displayed small equalities. These tests certify the construction and arithmetic, not optimality at unproved parameters. The full matching lower bound remains unresolved by this attempt.

Sources

Go to contribution →