Crossing numbers of complete and complete bipartite graphs

Source and verification

This article explains family 165 of the October 6, 2026 OpenAI collection. Research conclusions are attributed to its manuscripts. The review covers statements, introductions, and selected proof mechanisms; it is not an independent verification of the complete proofs.

🏷️ Drawings and crossing numbers

A drawing of a finite graph places its vertices at distinct points of the plane and represents edges by continuous simple arcs. In a drawing in general position, crossings are proper intersections of two edge interiors, with no tangencies or triple crossings. The crossing number $\mathrm{cr}(G)$ is the minimum number of crossing points over such drawings.

Crossing points are counted individually. If two edges cross several times, each intersection contributes. The edges are not required to be straight segments, so this is the ordinary crossing number, not the rectilinear crossing number.

Let $K_n$ be the complete graph, and let $K_{m,n}$ be the complete bipartite graph with parts of sizes $m,n$.

Manuscript claims

For every $n\ge 1$, $\mathrm{cr}(K_n)=Z(n)$, where

$$\begin{array}{rl}Z(n)& =\frac{1}{4}\lfloor \frac{n}{2}\rfloor \lfloor \frac{n-1}{2}\rfloor \\ & \cdot \lfloor \frac{n-2}{2}\rfloor \lfloor \frac{n-3}{2}\rfloor .\end{array}$$

This is the Harary–Hill formula. (OpenAI, 2026)

For positive $m,n$, $\mathrm{cr}(K_{m,n})=d_m{d}_n$, where

$$d_j=\lfloor \frac{j}{2}\rfloor \lfloor \frac{j-1}{2}\rfloor .$$

This is the Zarankiewicz formula. (OpenAI, 2026a)

The complete-graph formula is zero for $n\le 4$, and gives one for $K_5$ and three for $K_6$. The bipartite formula gives one for $K_{3,3}$ and four for $K_{4,4}$. These checks illustrate the normalization; they do not establish the general lower bounds.

🏷️ Upper bounds versus lower bounds

Classical drawings attain the displayed quantities: a two-page arrangement for complete graphs and a balanced axes arrangement for complete bipartite graphs. Producing these drawings proves an upper bound. The new claim is that every allowed drawing has at least that many crossing points.

Both manuscripts seek lower bounds through linear algebra built from signed intersections. An oriented crossing carries a sign determined by the two tangent directions. Algebraic intersection counts can cancel, but the total number of crossing points is at least the magnitude of any corresponding signed count. The proofs exploit compatibility among many such counts, not just their individual magnitudes.

🏷️ Complete graphs: an isotropic dimension bound

For odd order $n=2s+1$, the target is

$$Z(2s+1)={\left(\genfrac{}{}{0ex}{}{s}{2}\right)}^2.$$

The manuscript constructs a polynomial space in four variables, symmetric in each pair of variables belonging to an edge, with degree at most $s-2$ in each variable. Symmetric polynomials in two variables with this individual degree bound have dimension $s(s-1)/2$. Taking two such pairs gives dimension ${\left(\genfrac{}{}{0ex}{}{s}{2}\right)}^2$.

Evaluation on ordered pairs of disjoint edges maps this polynomial space into coordinates associated with nonzero signed intersections. A carefully chosen interpolation argument proves injectivity. In outline, even-node Lagrange formulas detect vanishing along cross-diagonals; divisibility by the resulting factors permits the argument to repeat until a polynomial in the kernel must be zero.

The evaluated image is isotropic for a nondegenerate diagonal bilinear form arising from the intersection data. Here isotropic means that the form vanishes on every pair of vectors in the image. In a space of dimension $N$ with a nondegenerate bilinear form, an isotropic subspace $U$ satisfies $U\subseteq U^{\perp }$, so $2\dim U\le N$.

Ordered edge pairs contribute two coordinates per unordered pair. Combining injectivity, isotropy, and the fact that a nonzero signed intersection requires a crossing gives the desired lower bound. The topological input ensures that the intersection pairing and half-rotation correction satisfy the cycle identities used in the isotropy calculation.

For even $n>4$, vertex deletion transfers the odd-order bound. In a minimum drawing taken without crossings between adjacent edges, each crossing involves four vertices and survives deletion of any of the other $n-4$ vertices. Therefore

$$\begin{array}{rl}(n-4)\mathrm{cr}(K_n)& \ge n\mathrm{cr}(K_{n-1}),\\ \mathrm{cr}(K_n)& \ge \frac{n}{n-4}Z(n-1)\\ & =Z(n).\end{array}$$

The planar small cases are handled separately, avoiding division by zero.

🏷️ Complete bipartite graphs: a rank inequality

The companion uses a subspace inequality. If $U_i,V_i$ are subspaces of an $N$-dimensional space and $U_i\cap V_i=\{0\}$ for each $i=1,\dots ,m$, then the required estimate is

$$\sum _{i,j=1}^m\dim (U_i\cap V_j)\le \lfloor \frac{m^2}{4}\rfloor N.$$

The paper proves and applies this estimate to graphs of linear maps. Their intersections encode kernels of differences, converting geometric crossing information into rank restrictions.

For an odd part size $n=2s+1$, an interpolation operator transforms $n\times n$ arrays into $s^2\times s^2$ matrices. It kills contributions depending only on a row or only on a column; each individual entry contributes rank at most one. At the same time, the relevant half-order sign arrays map to invertible matrices.

Cycle relations allow the transformed crossing blocks to be expressed as differences $X_i-Y_j$, with the diagonal blocks invertible and the off-diagonal ranks bounded by crossing counts. The resulting rank inequality forces at least $d_m{d}_n$ crossings. Deleting vertices transfers the argument to even part sizes.

The two papers share a strategy but use different finite-dimensional mechanisms: an isotropic evaluation space in one, and intersections of graph subspaces in the other. In each, the pivotal claim is that the construction applies to every topological drawing, including drawings with repeated edge-pair crossings.

🏷️ Key steps and proof outlines

Complete graphs: force collision factors, then divide them away

For $n=2s+1$, let $\mathcal{S}$ be the polynomial space described above, of dimension ${\left(\genfrac{}{}{0ex}{}{s}{2}\right)}^2$. Write $\mathcal{T}$ for the ordered disjoint edge pairs with nonzero signed intersection count, and $E:\mathcal{S}\to {\mathbb{R}}^{\mathcal{T}}$ for evaluation at their endpoint parameters. The main proof must show that the possibly sparse support $\mathcal{T}$ still determines every polynomial. (OpenAI, 2026b)

Suppose $E(P)=0$. The source inserts $P$ into its cycle identity with the factor

$$(u-v)(u-y)(v-x)U(x)V(y)B(u,v).$$

The three differences kill three shared-endpoint coincidences; disjoint-edge terms vanish by the assumed kernel condition. Only the coincidence $x=y$ remains. Taking $\mathrm{deg}U,\mathrm{deg}V\le s$ lets the products $UV$ interpolate arbitrary values on the $2s+1$ node parameters. Thus each shared endpoint can be isolated separately. The local order detector then implies $P(t_i,u,t_i,v)=0$ for every node $t_i$.

The degree of $P(x,u,x,v)$ in $x$ is at most $2s-4<2s+1$, so its vanishing at all nodes forces it to vanish identically. Therefore $x-y$ divides $P$. The two within-edge symmetries give the other three factors, hence

$$P=(x-y)(x-v)(u-y)(u-v)R.$$

At every disjoint-edge evaluation the four-factor product is nonzero. Consequently $E(R)=0$, while $R$ has the same symmetries and smaller degree in every variable. Choosing a nonzero kernel polynomial of minimal degree gives a contradiction. This is the actual descent behind injectivity.

Why signed cancellation still yields a crossing lower bound

For $P,Q\in \mathcal{S}$, multiply $PQ$ by the product $\Delta$ of all six endpoint differences. Its separate degrees remain at most $2s-1$, within the cycle identity’s range. Shared-endpoint terms disappear, leaving

$$\sum _{\alpha \in \mathcal{T}}{a}_{\alpha }E(P{)}_{\alpha }E(Q{)}_{\alpha }=0,a_{\alpha }\ne 0.$$

The coefficients combine the signed crossing count, nonzero interpolation weights, and $\Delta$. This is a nondegenerate symmetric diagonal form, not the original skew intersection form. Exchanging the two whole edges yields another coordinate with opposite coefficient; it does not make the form degenerate.

Thus $E(\mathcal{S})\subseteq E(\mathcal{S}{)}^{\perp }$, forcing $2\dim \mathcal{S}\le |\mathcal{T}|$. Each unordered supported edge pair needs at least one actual crossing, so the number of crossings is at least $|\mathcal{T}|/2$. Repeated crossings may cancel their signs and remove a coordinate, but cannot invalidate this lower bound.

Bipartite graphs: turn intersections into polynomial zero multiplicities

The companion’s subspace lemma has a different proof. Given $U_i\cap V_i=0$ in an $N$-dimensional space, select distinct real nodes $t_i$. For a subspace $Z$, let ${\mathcal{P}}_h(Z)$ contain the $Z$-valued polynomials of degree at most $h$ whose values at $t_i$ lie in $U_i$. Put

$$k_h(Z)=\dim {\mathcal{P}}_h(Z)-\dim {\mathcal{P}}_{h-1}(Z).$$

Away from the nodes, evaluation has kernel $(\xi -t){\mathcal{P}}_{h-1}(Z)$, so its image dimension is exactly $k_h(Z)$. Interpolation at all nodes gives

$$\sum _{h=0}^{m-1}{k}_h(Z)=\sum _i\dim (U_i\cap Z).$$

Choose polynomial columns in stages, adding ${\ell }_e=k_e(W)-k_{e-1}(W)$ independent evaluation directions at degree $e$. A nonzero minor of the columns through stage $h$ has degree at most ${\sum }_{e\le h}e{\ell }_e$. At nonnodes, quotient evaluation by $V_j$ has rank at most $k_h(W)-k_h(V_j)$. Every larger polynomial minor therefore vanishes identically, so the same rank bound persists at $t_j$. At that node the quotient is injective on $U_j$, because $U_j\cap V_j=0$, forcing rank deficiency at least $k_h(V_j)$. A determinant with deficiency $q$ is divisible by $(\xi -t_j{)}^q$: after a constant column change, $q$ columns vanish at that node.

Summing the resulting multiplicity bounds yields

$$\begin{array}{rl}\sum _{i,j}\dim (U_i\cap V_j)& \le \sum _{e}e(m-e){\ell }_e\\ & \le \lfloor m^2/4\rfloor N.\end{array}$$

For graphs of matrices, $\dim (U_i\cap V_j)=d-\mathrm{rank}(X_i-Y_j)$, so this becomes the required rank-sum lower bound. (OpenAI, 2026a)

The drawing-to-matrix detector completes the connection: barycentric interpolation weights annihilate row-only and column-only errors; a single crossing coordinate contributes rank at most one; and a two-triangle interpolation pattern makes every spoke-order matrix invertible. The two triangles contain $s^2$ evaluations. Factoring one complete row and one column reduces the interpolation problem from $s$ to $s-1$, proving their independence. Thus topology supplies compatible differences, interpolation detects the diagonal orders, and the rank inequality forces the crossing count.

See Also

• Coloring and clique minors uses branch-set counting and matrix rank for different graph invariants.
• Second out-neighborhoods uses a rank-based pruning lemma to resolve an extremal counting obstruction.

🏷️ Manuscripts and verification scope

• The crossing number of complete graphs — pinned manuscript and companion source.
• The crossing number of complete bipartite graphs — pinned manuscript and companion source.

The family scope page describes selected formalization coverage. The two selections concern ordinary topological crossing numbers and matching drawings. Crossings are spatial points, including repeated crossings of the same edge pair. No Lean build, axiom audit, or manuscript-to-formal-statement equivalence check was performed for these notes.

OpenAI collection provides prerequisites and the reading sequence; coverage register records completed and pending families.

🐻  OpenAI 2026a. The crossing number of complete bipartite graphs.

🐻  OpenAI 2026b. The crossing number of complete graphs.