gpt 6 astra ultra attempt on Math-608

The Crossing Number of Complete Bipartite Graphs

Definitions and mathematical statement

Shared notation.

Unless a section says otherwise, ${\mathbb{N}}=\{1,2,\ldots\}$, ${\mathbb{Z}}$ is the ring of integers, ${\mathbb{Q}},{\mathbb{R}},{\mathbb{C}}$ are the rational, real, and complex fields, $[N]=\{1,\ldots,\lfloor N\rfloor\}$, and $\log$ is the natural logarithm. For real functions of a parameter tending to infinity, $f\ll g$ and $f=O(g)$ mean $|f|\leq Cg$ eventually for some fixed $C$; $f\gg g$ reverses this comparison; $f=o(g)$ means $f/g\to0$; $f\sim g$ means $f/g\to1$; and $f\asymp g$ means both order bounds. A subscript on $O$ or $\ll$ specifies allowed constant dependence. The expression $n^{o(1)}$ in an upper bound means growth smaller than $n^\epsilon$ for each fixed $\epsilon>0$. Local definitions govern any exception, finite-field convention, or use of the same symbol for another object. An asymptotic claim is not automatically an effective algorithm.

The graph $K_{m,n}$ has disjoint vertex classes of sizes $m,n$ and every possible edge between the classes, with no edges within a class. Crossing number permits arbitrary topological drawings. The familiar proposed value is \[Z(m,n)=\lfloor m/2\rfloor\lfloor(m-1)/2\rfloor\lfloor n/2\rfloor\lfloor(n-1)/2\rfloor.\] The source asks for the exact minimum, not merely the value of one explicit drawing. [S1] [S2]

Statement recorded in the supplied source.

What is the minimum crossing number of the complete bipartite graph $K_{m,n}$? [S1]

Residual task reported by the archive.

The embedded review $2026-08-17$ records: Prove Zarankiewicz's lower bound for all m,n or find a drawing with fewer than Z(m,n) crossings. [S1]

Short English statement

What is the fewest number of crossings needed to draw all connections between two groups of prescribed sizes?

Research attempt

Status: UNRESOLVED. We construct the proposed crossing-number upper bound and derive a universal lower bound by counting $K_{3,3}$ subdrawings. The resulting gap quantifies why averaging only the smallest obstruction cannot prove the full formula.

Literature and drawing model.

The primary abstract of de Klerk--Pasechnik [S3], checked 1 October 2026, concerns two-page crossing numbers. A lower bound for that restricted drawing model does not automatically lower-bound the unrestricted topological crossing number here. We use unrestricted drawings throughout. Standard local simplifications let a minimum drawing have no crossings between adjacent edges, no self-crossings, and no triple interior crossings: unnecessary crossings can be removed by rerouting and a small perturbation. Consequently every crossing involves two distinct vertices in each bipartition class.

An explicit drawing with $Z(m,n)$ crossings.

Split the $m$ vertices into groups of sizes $a=\lfloor m/2\rfloor$ and $b=\lceil m/2\rceil$, placing them at distinct nonzero points on the positive and negative horizontal rays respectively. Split the $n$ vertices similarly into sizes $c,d$ on the positive and negative vertical rays. Draw every cross-part edge as a straight segment. Its interior lies in exactly one open quadrant.

Within one quadrant, selecting two horizontal and two vertical points gives exactly one crossing between the two oppositely ordered connecting segments. This can be checked from the order of their endpoints around the boundary of their convex quadrilateral: its diagonals cross, while its sides do not. There are $\binom a2\binom c2$ such crossings in the corresponding quadrant. Summing the four quadrants gives \[ \left(\binom a2+\binom b2\right) \left(\binom c2+\binom d2\right) =\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. \] Choose coordinates generically, or make a small perturbation, to separate accidental triple crossings without changing which independent pairs cross. Edges in different open quadrants do not cross. This proves $\operatorname{cr}(K_{m,n})\le Z(m,n)$.

When either part has at most two vertices the formula is zero and the drawing is planar, so the target is fully proved in those boundary cases. For $m=n=3$ the construction has one crossing.

The $K_{3,3}$ obstruction.

Every simple bipartite planar graph with $v\ge3$ vertices has $e\le2v-4$, from Euler's formula and the fact that each facial boundary has length at least four after the usual handling of bridges. Since $K_{3,3}$ has six vertices and nine edges, it is not planar and every drawing has at least one crossing. Together with the preceding construction this proves $\operatorname{cr}(K_{3,3})=1$.

Now take a drawing of $K_{m,n}$ with $C$ crossings, $m,n\ge3$, and restrict it to every choice of three vertices on each side. Each resulting $K_{3,3}$ drawing has a crossing, so the total number of crossing occurrences in these subdrawings is at least $\binom m3\binom n3$.

A crossing of two independent edges uses two vertices on each side and appears in exactly $(m-2)(n-2)$ of these subdrawings. Double counting yields \[ C\ge\frac{\binom m3\binom n3}{(m-2)(n-2)} =\frac{m(m-1)n(n-1)}{36}. \] Since $C$ is an integer it may be rounded upward. This lower bound holds for arbitrary topological drawings and not just the axes construction.

What larger subdrawings would provide.

If a rigorously established lower bound $L_{s,t}$ is known for $K_{s,t}$, the same argument gives \[ C\ge L_{s,t}\, \frac{m(m-1)n(n-1)}{s(s-1)t(t-1)} \qquad(m\ge s\ge2,\ n\ge t\ge2). \] Each crossing belongs to $\binom{m-2}{s-2}\binom{n-2}{t-2}$ selected subdrawings; division by that multiplicity proves the formula. This clarifies how finite exact crossing results can improve a global lower bound, while also showing that the constants, not just the existence of a nonplanar subgraph, matter.

For the elementary $s=t=3$ input, the leading coefficient is $1/36$, while the proposed upper bound has leading coefficient $1/16$ when both parts grow. Their ratio tends to $4/9$. Rounding cannot close a gap of that order. Assuming every subdrawing simultaneously realizes its own minimum ignores compatibility among their overlapping edges and rotation systems.

Verification and exact gap.

At $(m,n)=(3,3)$ both estimates equal one. In the axes drawing, crossings were counted by unordered choices of two vertices on each ray, so no factor of two is missing. In the lower bound, the multiplicity was counted by adding one unused vertex to each already selected pair. No finite drawing search or new best constant is claimed.

The remaining task is a lower bound matching $Z(m,n)$ for every pair, or an explicit unrestricted drawing with fewer crossings. The missing information in this attempt is the dependence between overlapping small subdrawings. Restricting all vertices to a spine or to the four rays may simplify optimization but would narrow the class of competitors and cannot prove the required universal lower bound by itself.

Sources

• S1 ULAM.AI, UnsolvedMath, supplied problems.json, record 1407 (GRAPH-020), statement and background. The embedded literature-review date is 2026-08-17; that is the archive’s review date, not a fresh certification. Dataset landing page: https://huggingface.co/datasets/ulamai/UnsolvedMath.

• S2 J. Balogh, B. Lidický, S. Norin, F. Pfender, G. Salazar, and S. Spiro, Crossing numbers of complete bipartite graphs, Procedia Computer Science 223 $2023$, 78–87. https://doi.org/10.1016/j.procs.2023.08.216. Bibliographic information from the supplied record.

• S3 E. de Klerk and D. V. Pasechnik, Improved lower bounds for the 2-page crossing numbers of K_{m,n} and K_n via semidefinite programming, arXiv:1110.4824. https://arxiv.org/abs/1110.4824. Bibliographic information from the supplied record.