Exact crossing counts for complete and complete bipartite graphs

← All digests

Family 165 · Combinatorics
Importance 5/5 · Provisional editorial rating
Sources consulted 2026-10-11

1. The question

Draw a network in the plane, with a point for each vertex and a curve for each edge. Dense networks force some edges to cross. How few crossings can be achieved if one is free to move every vertex and reroute every edge?

Two particularly symmetric networks have resisted exact answers. The complete graph connects every pair of vertices. The complete bipartite graph connects every vertex in one group to every vertex in another. Classical drawings give simple formulas for their crossing counts, but proving that no more ingenious drawing improves them is a different task.

Family 165 contains two manuscripts claiming those exact minima: the Harary–Hill formula for complete graphs and the Zarankiewicz formula associated with Turán’s brickyard problem for complete bipartite graphs. Their common approach turns information about crossings and the order of edges around vertices into linear-algebraic lower bounds.

2. Background and essential definitions

A plane drawing places vertices at distinct points and represents each edge by a simple continuous arc. Edge interiors avoid vertices. Crossings are proper crossings of two arcs, with finitely many such points and no tangencies, overlaps or triple crossings.

Let $c(D)$ be the number of crossing points in a drawing $D$. The ordinary crossing number is

$$\operatorname{cr}(G)=\min_D c(D).$$

If the same two edges cross several times, every crossing counts. This differs from counting intersecting edge pairs once or counting only pairs that cross an odd number of times. It also differs from requiring straight edges: curved arcs provide additional freedom.

The complete graph $K_n$ has $n$ vertices and $\binom n2$ edges. The complete bipartite graph $K_{m,n}$ has parts of sizes $m,n$, all $mn$ cross-part edges, and no within-part edges.

A drawing with $C$ crossings proves $\operatorname{cr}(G)\le C$. To establish equality one must also show that every permissible drawing has at least $C$ crossings. The upper bound is constructive; the lower bound quantifies over all arrangements.

For example, $K_3$ and $K_4$ can be drawn without crossings, whereas $K_5$ needs one. Likewise, $K_{2,n}$ is planar for every $n$, while $K_{3,3}$ needs one crossing. These small examples help explain the zero and one values produced by the claimed formulas.

3. Development history and previous partial results

Turán traced the bipartite problem to railway connections between kilns and storage yards in a brick factory in 1944. Zarankiewicz gave the classical balanced-axis construction and a proposed optimality argument, but the lower-bound argument contained a gap. Turán’s own account appears in A note of welcome, and the original construction is in Zarankiewicz’s paper.

Kleitman established the bipartite formula when one part has at most six vertices. Woodall developed methods based on the cyclic order of incident edges and verified further cases computationally. Later semidefinite and flag-algebra techniques gave increasingly strong lower bounds. The new manuscript cites a balanced-case asymptotic ratio of at least 0.9118 to the conjectured value, illustrating both substantial progress and the remaining gap.

For complete graphs, Harary and Hill’s 1963 paper described Hill’s construction and the proposed formula, crediting Guy with an earlier published upper bound. Exact small cases and asymptotic estimates followed. The lower-bound ratio eventually exceeded 0.98559895, as recorded in Balogh, Lidický and Salazar’s work.

Another line of progress proved the formula for restricted drawings. The two-page theorem places all vertices on a line and routes each edge within one of its two half-planes. Shellability and other geometric conditions covered further classes. These results show that many natural optimal drawings obey the prediction, but do not control every unrestricted drawing.

Tutte’s algebraic approach and Woodall’s local-order methods are methodological predecessors of this family. The new sources claim to combine topology, signed crossings and polynomial interpolation in a way that removes restrictions on the drawing.

4. What the new manuscripts claim

M1 states that, for every positive integer $n$,

$$\operatorname{cr}(K_n)= \frac14 \left\lfloor\frac n2\right\rfloor \left\lfloor\frac{n-1}{2}\right\rfloor \left\lfloor\frac{n-2}{2}\right\rfloor \left\lfloor\frac{n-3}{2}\right\rfloor.$$

The floor $\lfloor x\rfloor$ rounds down to an integer. The zero values for $n=1,2$ agree with their crossing-free drawings. For $n=5$, the product gives one; for $n=6$, it gives three.

M2 states that, for all 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.$$

For $K_{3,3}$, this again gives one. When either part has size at most two, one factor vanishes, agreeing with planarity.

Both formulas concern unrestricted ordinary drawings with continuous edge arcs. They establish exact finite values, including parity effects, rather than merely leading asymptotic constants. Their leading orders are $n^4/64$ for $K_n$ and $m^2n^2/16$ when both bipartite part sizes grow.

The complete-graph paper explicitly states that its lower bound does not depend on the bipartite crossing-number formula. The papers share an algebraic viewpoint, but the two headline theorems are not presented as a simple implication from one another.

5. Why the advance matters

Importance: 5/5. These are two central exact problems in topological graph theory. Their formulas have long been easy to realize by drawings and difficult to prove unavoidable. A proof for every unrestricted drawing would complete a much stronger statement than an asymptotic approximation or a restricted-class theorem.

The method also changes what a lower-bound certificate can look like. Instead of trying to inspect all possible pictures, the source extracts a finite-dimensional algebraic object whose required dimension forces enough crossing data.

The result would provide exact benchmarks for two fundamental dense graph families. It does not make crossing-number computation easy for arbitrary graphs, but it would settle unusually prominent cases against which general methods are compared.

6. The main idea

Add signs and local edge orders

Give each edge an orientation. At a crossing, the ordered pair of tangent directions determines a positive or negative sign. Signed crossing counts can cancel, so by themselves they do not measure the number of crossings. Their value is algebraic consistency.

At each vertex, also record the circular order of the incident edges. The manuscript combines interior signed intersections with a correction derived from that local order. The corrected bilinear pairing vanishes when applied to cycles.

This reflects a planar topological principle: appropriately counted algebraic intersections of closed plane curves cancel. The local correction accounts for cycles that share graph vertices, where one cannot treat their edge interiors as completely disjoint closed curves.

Detect order through interpolation

For the bipartite problem, the source builds a linear transformation of crossing-data matrices. It annihilates irrelevant row-plus-column terms, while the comparison-sign matrix of any local linear order is sent to an invertible matrix.

The transformation uses Lagrange interpolation: a polynomial of bounded degree is determined by its values at enough distinct nodes. Here the construction uses several variables and symmetry to turn local order into full rank. Meanwhile, an individual crossing contributes a matrix of rank at most one.

A separate inequality for pairs of subspaces bounds the total dimensions of certain intersections. Applied to graphs of linear maps, it becomes a lower bound on a sum of ranks. Full-rank diagonal information and the cycle identity then force enough off-diagonal rank, hence enough crossings. The resulting count matches the balanced-axis construction.

A polynomial space forces the complete-graph count

For odd $n=2s+1$, M1 considers polynomials in four variables representing the endpoints of two edges. The polynomials are symmetric in each edge’s endpoints and have bounded degree. The space has dimension equal to the desired crossing formula.

Evaluation at edge pairs with nonzero signed crossing count must determine each polynomial. The source proves this by using the cycle identity to force vanishing at coincident endpoints, dividing out the resulting factors and descending in degree. A nonzero polynomial cannot survive indefinite degree reduction.

An additional pairing argument makes the evaluation image totally isotropic, meaning every two vectors in it pair to zero under a specified nondegenerate form. Linear algebra bounds such a subspace by half the ambient dimension. Since the coordinates arise from crossing edge pairs, the dimension requirement yields the lower bound.

Vertex deletion transfers the odd-order conclusions to even orders. Classical drawings supply the matching upper bounds. The topology provides identities, interpolation makes them detect enough information, and dimension counting converts that information into unavoidable crossings.

7. Scope, limitations, and open questions

The formulas apply to ordinary point-count crossing numbers. They should not be substituted for straight-line, pair-crossing, odd-crossing or surface-crossing parameters, whose optimization problems differ.

The statements permit arbitrary vertex positions and continuous edge routes subject to the drawing conventions. Normalizing a minimizing drawing to polygonal arcs and removing adjacent-edge crossings is part of the source’s treatment, rather than an extra hypothesis imposed on the theorem.

These exact values do not classify every optimal drawing. Different arrangements may attain the same count, and uniqueness or structural classification would require further results. Nor do the formulas provide an efficient general algorithm for the crossing number of any input graph.

The papers’ algebraic inequalities may suggest broader applications, but such extensions would need their own connection between crossing data and rank. The claims summarized here concern precisely the two complete graph families.

8. Sources and further reading

Theorem 1.1 in each manuscript gives its exact formula. Their early sections define the ordinary crossing convention and establish the corrected cycle pairing. M2’s Sections 2 and 4 contain the subspace and order-detection ingredients; M1’s Sections 3–4 give the polynomial-space argument. Both include the relevant drawing reductions.

The primary historical links above distinguish classical constructions, partial lower bounds and restricted-drawing theorems. Wikipedia’s crossing number page is optional background for small graph illustrations.

Source manuscripts

• M1. OpenAI, The crossing number of complete graphs (September 23, 2026).
• M2. OpenAI, The crossing number of complete bipartite graphs (September 23, 2026).

Sources consulted on 11 October 2026 at repository revision fd4aeeb. Download the manuscript citations.