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

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3319 (OPG-310), OpenGarden collection. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, The Crossing Number of the Complete Bipartite Graph. Original problem and discussion; the mathematical formulation below is expanded from the supplied source record. http://www.openproblemgarden.org/op/the_crossing_number_of_the_complete_bipartite_graph.