Overview. Introduction to the proof: from subspaces to crossings [cn-0070]
The first ingredient is an inequality about subspaces. Fix an integer \(m\geq 1\), a real vector space \(W\) of finite dimension \(N\), and two indexed families of linear subspaces \(U_1,\ldots ,U_m\) and \(V_1,\ldots ,V_m\) of \(W\). Suppose \(U_i\cap V_i=\{0\}\) for every \(i\). The subspace-intersection inequality [cn-0024] states that
\[\sum _{i,j=1}^{m}\dim (U_i\cap V_j)\leq \left \lfloor \frac {m^2}{4}\right \rfloor N.\tag{1.2}\]The sum runs over all \(m^2\) ordered pairs of indices. Its diagonal terms, with \(i=j\), are zero by hypothesis; intersections with \(i\ne j\) can have positive dimension. Thus (1.2) bounds the total of these intersection dimensions in terms of the number of pairs of subspaces and the dimension of their common ambient space.
To prove this inequality, choose distinct real interpolation nodes [cn-0063] \(t_1,\ldots ,t_m\) and consider univariate polynomial maps [cn-0064] \(P:\mathbb R\to W\) subject to \(P(t_i)\in U_i\). The constrained evaluation spaces [cn-0019] record how their values can vary as the degree increases. Determinant multiplicity [cn-0021] turns the restrictions at the nodes into a bound on polynomial degrees. The algebraic branch [cn-0061] gives the complete argument leading to (1.2).
The useful consequence for crossings is a bound on matrix ranks. Fix a positive integer \(d\), and let \(X_1,\ldots ,X_m\) and \(Y_1,\ldots ,Y_m\) be real \(d\times d\) matrices. Here \(\operatorname {rank}\) is the dimension of the image of the corresponding linear map on \(\mathbb R^d\). Assume every diagonal difference \(X_i-Y_i\) is invertible. Apply (1.2) in the ambient space \(W=\mathbb R^d\oplus \mathbb R^d\), of dimension \(N=2d\), to the graph subspaces [cn-0026]
\[\begin {aligned}
U_i&=\Gamma _{X_i}=\{(v,X_iv):v\in \mathbb R^d\},\\
V_j&=\Gamma _{Y_j}=\{(v,Y_jv):v\in \mathbb R^d\}.
\end {aligned}\]A vector belongs to both graphs exactly when its first coordinate \(v\) satisfies \((X_i-Y_j)v=0\). Hence
\[\dim (U_i\cap V_j)=d-\operatorname {rank}(X_i-Y_j).\]In particular, invertibility of \(X_i-Y_i\) gives the required diagonal disjointness. Recall the balanced pair count [cn-0006] \(d_r=\lfloor r/2\rfloor \lfloor (r-1)/2\rfloor \) for a positive integer \(r\). Substituting the displayed dimension formula into (1.2) and removing the \(m\) diagonal rank terms gives the rank-sum corollary [cn-0027]:
\[\sum _{i\ne j}\operatorname {rank}(X_i-Y_j)\geq 2d_m d.\]This sum is again over ordered pairs. The integer \(d\) is the size of the matrices; the subscripted integer \(d_m\) is the balanced pair count determined by \(m\). We will construct matrices whose off-diagonal ranks are bounded by crossings and whose diagonal differences are invertible.
For the main part of the drawing argument, assume \(m\geq 3\) and \(n=2s+1\geq 3\), where \(s\) is a positive integer. Set \(d=s^2\); then \(d=d_n\). The second algebraic ingredient is the linear rank detector [cn-0032]
\[\Phi :\mathbb R^{n\times n}\longrightarrow \mathbb R^{d\times d}.\]Its input and output sizes serve different purposes: an input matrix will compare the \(n\) edges in one vertex star with the \(n\) edges in another, while the output will enter the rank-sum inequality above. Three properties of \(\Phi \) make this possible.
First, let \(\mathcal L\subseteq \mathbb R^{n\times n}\) be the space of row-plus-column matrices [cn-0017]: matrices \(H\) whose entries have the form \(H(p,q)=r_p+c_q\) for some vectors \(r,c\in \mathbb R^n\). The detector annihilates [cn-0033] both \(\mathcal L\) and every diagonal input matrix. Adding either kind of matrix to \(H\) therefore leaves \(\Phi (H)\) unchanged.
Second, the contribution of a single input entry to \(\Phi (H)\) has rank at most one, and a diagonal input entry contributes zero. Consequently the support rank bound [cn-0033] gives, for every \(H\in \mathbb R^{n\times n}\),
\[\operatorname {rank}\Phi (H)\leq \#\{(p,q):1\leq p,q\leq n,\ p\ne q,\ H(p,q)\ne 0\}.\]The right-hand side counts the nonzero off-diagonal entries of \(H\). This is how a bound on matrix entries will become a bound on crossings.
Third, for a linear order \(\prec \) on \(\{1,\ldots ,n\}\), let \(S_\prec \) be its half-order matrix [cn-0011]: its entry is \(+1/2\) when \(p\prec q\), \(-1/2\) when \(q\prec p\), and \(0\) when \(p=q\). The order-invertibility lemma [cn-0034] proves
\[\operatorname {rank}\Phi (S_\prec )=d\qquad \text {for every linear order }\prec .\]The same map \(\Phi \) works for all these orders. The detector branch [cn-0062] constructs it from barycentric weights [cn-0030] and bivariate evaluation vectors [cn-0028], using one fixed tuple of distinct real nodes. Two-triangle interpolation [cn-0029] supplies the invertibility argument.
We now obtain the input matrices from a drawing. Write the vertex classes of \(K_{m,n}\) [cn-0002] as \(\{a_1,\ldots ,a_m\}\) and \(\{b_1,\ldots ,b_n\}\). Begin with any admissible drawing [cn-0004] \(D_0\). By normalization [cn-0009], replace it by a normalized drawing [cn-0008] \(D\), with polygonal edges and no adjacent-edge crossings, such that its crossing count [cn-0005] satisfies \(c(D)\leq c(D_0)\). A lower bound for \(c(D)\) will therefore give the same lower bound for \(c(D_0)\).
Orient the edge \(a_i b_p\) from \(a_i\) to \(b_p\), and abbreviate it to \(ip\). We use \(i,k\in \{1,\ldots ,m\}\) for first-class vertices and \(p,q\in \{1,\ldots ,n\}\) for second-class vertices. The star at \(a_i\) [cn-0002] consists of its \(n\) incident edges \(i1,\ldots ,in\).
At each vertex \(v\), choose a gap between outward spokes and read them counterclockwise from that gap. The resulting spoke comparison sign [cn-0011] \(T_v(e,f)\) is \(+1\) if the spoke of \(e\) precedes that of \(f\), \(-1\) for the reverse order, and \(0\) if \(e=f\). For two distinct oriented edges \(e,f\), let \(I(e,f)\) be their signed interior intersection count [cn-0010], summing the signs of all their crossing points.
The endpoint-corrected intersection matrix [cn-0013] \(J\) is a real \(mn\times mn\) matrix whose rows and columns are indexed by edges. Set \(J(e,e)=0\). If \(e,f\) are independent, set \(J(e,f)=I(e,f)\); if they share a vertex \(v\), add the endpoint term \(\tfrac 12T_v(e,f)\). This form of the endpoint term uses our orientation: at any shared vertex, both incident edges point outward or both point inward.
Group the edges by their first-class endpoints. The resulting \(n\times n\) star block [cn-0013] \(J^{ik}\) compares the star at \(a_i\) with the star at \(a_k\):
\[J^{ik}(p,q)=J(ip,kq).\]The endpoint corrections make the cycle-pairing identity [cn-0016] hold. Its topological input is that the mutual signed intersection [cn-0069] of two closed polygonal walks meeting transversely away from their corners in the plane is zero [cn-0015]. Applying the cycle identity to suitable four-cycles gives the additive block relation [cn-0018]
\[J^{ik}-J^{i1}-J^{1k}+J^{11}\in \mathcal L.\]Here \(a_1\) is a fixed reference vertex, and \(\mathcal L\) is the row-plus-column space defined above. Apply \(\Phi \) to each block and write \(R^{ik}=\Phi (J^{ik})\), a \(d\times d\) matrix. Since \(\Phi \) annihilates \(\mathcal L\), the relation becomes \(R^{ik}=R^{i1}+R^{1k}-R^{11}\). Thus setting
\[X_i=R^{i1},\qquad Y_k=R^{11}-R^{1k}\]gives precisely the required difference form \(R^{ik}=X_i-Y_k\). These are the matrices to which we apply the rank-sum corollary.
On the diagonal, all edges in the star at \(a_i\) share that vertex, so normalization has removed their interior crossings. Therefore \(J^{ii}\) is exactly the half-order matrix [cn-0011] of the spoke order at \(a_i\). The detector's invertibility property gives \(\operatorname {rank}R^{ii}=d\); equivalently, every \(X_i-Y_i\) is invertible. This concerns diagonal star blocks, each an \(n\times n\) matrix, rather than diagonal entries within an input matrix.
For \(i\ne k\), let \(c_{ik}\) be the number of crossing points between an edge in the star at \(a_i\) and an edge in the star at \(a_k\). In \(J^{ik}\), entries with \(p=q\) can have an endpoint correction at \(b_p\), but the detector annihilates these diagonal input entries. For \(p\ne q\), the two edges \(ip,kq\) are independent, so \(J^{ik}(p,q)=I(ip,kq)\). Each nonzero such entry requires at least one crossing of that pair. The support rank bound therefore yields
\[\operatorname {rank}R^{ik}\leq c_{ik}\qquad (i\ne k).\]The count \(c_{ik}\) includes every crossing point, even when the same two edges cross repeatedly. Cancellation between positive and negative crossings can make a signed entry smaller or zero; it does not invalidate this rank bound.
The odd-size lower bound [cn-0035] now follows by putting the two rank estimates together, using \(d=d_n\):
\[2d_m d_n\leq \sum _{i\ne k}\operatorname {rank}R^{ik}\leq \sum _{i\ne k}c_{ik}=2c(D).\]Both sums run over ordered pairs of distinct first-class indices. Every crossing of the normalized drawing involves two distinct first-class stars and is counted once in each order, which explains the factor \(2\) on the right. Dividing by \(2\) gives \(c(D)\geq d_m d_n\), and hence \(c(D_0)\geq d_m d_n\).
For even \(n>2\), the vertex-deletion argument [cn-0037] transfers the lower bound from odd second-class sizes. The balanced-axis construction [cn-0036] gives a drawing with exactly \(d_m d_n\) crossings, supplying the matching upper bound. If either class has at most two vertices, this upper bound is zero. Together these steps prove the crossing-number formula [cn-0007].
- Proof dependencies
- None.
- Provenance
- OpenAI, 23 September 2026 [cn-0042], Section 1, from the paragraph containing equation (1.2) to the end of the introduction; rewritten with explicit notation and links on 9 October 2026.