THE CROSSING NUMBER OF COMPLETE BIPARTITE GRAPHS
A complete proof of the Zarankiewicz conjecture, written for curious high
school students.
==============================================================================
CONTENTS
==============================================================================
Part I Setting the scene Sections 1-3
Part II The upper bound Section 4
Part III The lower bound plan Section 5
Part IV Algebraic tools Sections 6-8
Part V Geometric machinery Sections 9-12
Part VI The rank detector Sections 13-15
Part VII The odd case Section 16
Part VIII The even case Section 17
Part IX Normalizing a drawing Section 18
Part X Further reading Section 19
==============================================================================
==============================================================================
PART I SETTING THE SCENE
==============================================================================
1. THE PROBLEM
1.1 Graphs. A GRAPH has VERTICES (points) and EDGES (curves joining
pairs of vertices). We assume no loops (a vertex joined to itself) and
no multiple edges between the same pair of vertices.
1.2 Complete bipartite graphs. K_{m,n} has two vertex classes,
A = {a_1, ..., a_m} (first class, or "kilns"),
B = {b_1, ..., b_n} (second class, or "yards"),
with an edge a_i b_j for every (i,j) and no other edges. Total edges: mn.
Picture: m kilns at one place, n yards at another, every kiln linked to
every yard by a railway.
1.3 Drawings and crossings. A DRAWING places the vertices at distinct
points of the plane and represents each edge by a simple arc whose
interior avoids all other vertices. A PROPER CROSSING is a point where
the interiors of two edges meet transversally (like the strokes of an X,
not a tangency). A drawing is ADMISSIBLE if:
(a) it has finitely many crossings;
(b) all crossings are proper;
(c) no three edges cross at one interior point;
(d) no tangencies and no shared arcs.
A nonadmissible drawing can always be nudged into an admissible one
without increasing the crossing count.
The CROSSING NUMBER of G is
cr(G) = min over admissible D of c(D),
where c(D) counts crossing POINTS (if a pair of edges crosses twice,
that is two crossings).
1.4 The formula. Define the Zarankiewicz number
d_r = floor(r/2) * floor((r-1)/2)
= C(floor(r/2), 2) + C(ceil(r/2), 2),
where C(n,2) = n(n-1)/2 is "n choose 2".
THEOREM (Zarankiewicz conjecture). For all m, n >= 1,
cr(K_{m,n}) = d_m * d_n.
The rest of the document proves this completely.
2. THE d-SEQUENCE AND SMALL CASES
2.1 Values. The Zarankiewicz numbers satisfy
d_{2s} = s(s-1),
d_{2s+1} = s^2.
Specifically:
r: 1 2 3 4 5 6 7 8 9 10
d_r: 0 0 1 2 4 6 9 12 16 20
2.2 Small cases, all consistent with the theorem.
cr(K_{1,n}) = 0 (a star; planar)
cr(K_{2,n}) = 0 (a double fan; planar)
cr(K_{3,3}) = 1 (three houses, three utilities:
K_{3,3} is nonplanar, but one crossing
achieves it)
cr(K_{4,4}) = 4 (Kleitman 1970)
cr(K_{7,7}) = 81 (Woodall 1993, by computer search)
2.3 Background. Turan posed the brick-factory problem around 1944.
Zarankiewicz (1955) built the balanced-axis drawing (Section 4) and
claimed optimality, but his argument had a gap. For seventy years no
one closed it. Even the previous best asymmetric lower bound, by
Balogh, Lidicky, Norin, Pfender, Salazar and Spiro (2023), reached only
cr(K_{n,n}) >= 0.9118 * d_n^2 + o(n^4) - close but not exact. This
document gives the exact formula with a complete proof.
3. THE PLAN
3.1 Two inequalities suffice.
Upper bound: cr(K_{m,n}) <= d_m d_n. Exhibit ONE drawing.
Lower bound: cr(K_{m,n}) >= d_m d_n. Show EVERY drawing crosses
at least d_m d_n times.
3.2 The upper bound is a specific construction (Section 4).
The lower bound is hard: no matter how cleverly you bend the edges,
the crossing count cannot drop below d_m d_n. We prove it by turning
the geometry into linear algebra:
(a) From any drawing, build a signed crossing matrix J whose
entries are signed intersection numbers of oriented edges.
(b) Closed loops give linear relations ("cycle pairing"). This
makes every block-difference J^{ik} - J^{i1} - J^{1k} + J^{11}
"additive" (row plus column).
(c) A linear map Phi (called the rank detector) sends each block
J^{ik} to a matrix R_ik = X_i - Y_k, with X_i - Y_i
invertible.
(d) A linear-algebra inequality (Section 8) forces
sum_{i != k} rank(R_ik) >= 2 d_m d_n.
(e) Each off-diagonal R_ik is bounded by the crossing count c_ik
between stars i and k.
(f) So 2 c(D) = sum c_ik >= sum rank(R_ik) >= 2 d_m d_n.
3.3 Roadmap.
Sections 6-8 linear algebra.
Sections 9-12 geometry of drawings, cycle pairing, block
additivity.
Sections 13-15 the detector Phi.
Section 16 odd n finishing.
Section 17 even n via vertex deletion.
Section 18 normalization of arbitrary drawings.
==============================================================================
PART II THE UPPER BOUND
==============================================================================
4. THE BALANCED-AXIS DRAWING
4.1 Goal. Draw K_{m,n} with exactly d_m d_n crossings.
4.2 Construction. Set
u = floor(m/2), u' = m - u = ceil(m/2),
v = floor(n/2), v' = n - v = ceil(n/2).
Place:
u A-vertices on the positive y-axis,
u' A-vertices on the negative y-axis,
v B-vertices on the positive x-axis,
v' B-vertices on the negative x-axis.
Draw every edge as a straight segment. All positions distinct, none at
the origin.
4.3 Crossings in the NE quadrant. An edge lies in the open quadrant
x>0, y>0 iff its A-endpoint is one of the upper vertices and its
B-endpoint is one of the right vertices.
Fix two upper A-vertices and two right B-vertices. The four points lie
on the two positive coordinate axes, forming a convex quadrilateral.
Its two diagonals each join an A-vertex to a B-vertex, so both are
edges of K_{m,n}; diagonals of a convex quadrilateral cross exactly
once, so these two edges cross inside the quadrant. Conversely every
NE crossing arises as the "diagonal pairing" of some choice of two
A-vertices and two B-vertices. (Which of the two possible pairings is
the diagonal one depends on the relative orders of the four points
along the two axes, but exactly one always is.)
So the number of NE-quadrant crossings equals
C(u, 2) * C(v, 2).
4.4 All four quadrants. Every edge lies in exactly one of the four
open quadrants. Its A-endpoint has a nonzero y-coordinate, whose sign
determines upper (positive) or lower (negative); its B-endpoint has a
nonzero x-coordinate, whose sign determines right (positive) or left
(negative). Summing contributions:
NE: C(u, 2) * C(v, 2)
NW: C(u, 2) * C(v', 2)
SE: C(u', 2) * C(v, 2)
SW: C(u', 2) * C(v', 2)
Total:
(C(u,2) + C(u',2)) * (C(v,2) + C(v',2)) = d_m * d_n,
using C(floor(r/2),2) + C(ceil(r/2),2) = d_r.
4.5 Why balanced split. With u + u' = m fixed, C(u,2) + C(u',2) is a
convex quadratic in u minimized at u = m/2. Hence the balanced split
u = floor(m/2), u' = ceil(m/2) is optimal. Same for v, v'.
4.6 Triple crossings. Three of the straight segments could conceivably
concur at one point. For fixed m,n that concurrence is a polynomial
condition on the axis coordinates. The set of positions avoiding all
such triple events is dense and open, so a small generic perturbation
removes all triple events without changing any of the double crossings
(the double crossings are stable). Therefore an admissible drawing
with exactly d_m d_n crossings exists.
4.7 Conclusion. cr(K_{m,n}) <= d_m d_n. If m <= 2 or n <= 2 then
d_m d_n = 0, matching the trivial lower bound.
==============================================================================
PART III THE PLAN FOR THE LOWER BOUND
==============================================================================
5. STRATEGY
5.1 Fix m,n and a MINIMUM drawing D of K_{m,n}. By Section 18, D may
be assumed polygonal, straight near every vertex and crossing, with
no crossing between edges that share a vertex.
We call these "adjacent edges", and they never cross in a normalized
drawing.
5.2 Three ingredients.
(GEOMETRY) Signed crossing matrix J with n x n blocks J^{ik},
satisfying
J^{ik} - J^{i1} - J^{1k} + J^{11} is additive.
[Sections 9-12]
(DETECTOR) Linear Phi : R^{n x n} -> R^{d x d} with:
Phi(H) = 0 for additive H and diagonal H;
Phi(E_pq) has rank <= 1 for every standard matrix E_pq;
Phi(S_prec) is invertible for every strict total
order prec on {1,...,n}.
[Sections 13-15]
(ALGEBRA) If X_1,...,X_m and Y_1,...,Y_m are d-by-d with every
X_i - Y_i invertible, then
sum_{i!=k} rank(X_i - Y_k) >= 2 d_m d.
[Sections 6-8]
5.3 How they click together. Apply Phi to the blocks of J.
Set R_ik = Phi(J^{ik}).
Additivity + annihilation:
R_ik = Phi(J^{i1}) + Phi(J^{1k}) - Phi(J^{11}) = X_i - Y_k,
where X_i = R_i1 and Y_k = R_11 - R_1k.
Diagonal: X_i - Y_i = R_ii = Phi(J^{ii}) is invertible by (iii).
Off-diagonal: rank(R_ik) <= c_ik.
Algebra forces
2 d_m d_n <= sum_{i!=k} rank(R_ik) <= sum_{i!=k} c_ik = 2 c(D).
5.4 Roadmap.
Sections 6-8 linear algebra.
Sections 9-12 signed intersections and block relations.
Sections 13-15 detector.
Section 16 odd n done.
Section 17 even n reduced to odd n.
Section 18 normalization.
==============================================================================
PART IV ALGEBRAIC TOOLS
==============================================================================
6. LINEAR ALGEBRA CRASH COURSE
6.1 Vector spaces. A real vector space V has + and scalar multiplication,
obeying the obvious rules. Examples: R^N and R^{a x b} (a-by-b real
matrices).
6.2 Subspaces. A SUBSPSACE U of V is a subset that contains 0 and is
closed under + and scalar multiplication. If U and V are subspaces of
W, so are U cap V = {w : w in U and w in V} and U + V = {u+v}.
6.3 Independence, basis, dimension. A list v_1,...,v_k is INDEPENDENT
if sum c_i v_i = 0 forces all c_i = 0. A BASIS is a spanning
independent list. Its size is the DIMENSION (uniquely defined).
6.4 Linear maps. T : V -> W is LINEAR if T(av + bw) = a T(v) + b T(w).
The KERNEL ker T = {v : T(v) = 0} and IMAGE im T = {T(v) : v in V} are
subspaces. Rank-nullity:
dim V = dim ker T + dim im T.
6.5 Matrices. An a-by-b real matrix M acts on R^b by x -> Mx.
rank M = dim im M;
nullity M = dim ker M = b - rank M;
M square is INVERTIBLE iff rank M = b.
Rank facts:
rank(A + B) <= rank A + rank B (subadditivity)
rank(A B) <= min(rank A, rank B) (submultiplicativity).
6.6 Polynomials. A nonzero real polynomial of degree <= k has at most
k distinct real roots. So if a polynomial of degree <= k vanishes at
k+1 distinct reals, it is identically zero; and if two such polynomials
agree at k+1 distinct reals, they are equal.
7. THE SUBSPACE INTERSECTION LEMMA
7.1 Statement. Let W be a real vector space of dimension N, and let
U_1,...,U_m and V_1,...,V_m be subspaces of W with
U_i cap V_i = {0} for every i.
Then
sum_{i,j=1}^m dim(U_i cap V_j) <= floor(m^2/4) * N.
7.2 Sharpness. Fix a direct-sum decomposition W = P + Q. Put
(U_i, V_i) = (P, Q) for i in the first floor(m/2) indices and
(Q, P) for the remaining ceil(m/2) indices. Every diagonal intersection
is {0}, and the off-diagonal sum is
floor(m/2) ceil(m/2) * (dim P + dim Q)
= floor(m^2/4) * N,
matching the bound. So the constant floor(m^2/4) is exact.
7.3 Proof. Fix distinct real numbers t_1, ..., t_m ("nodes").
For a subspace Z of W and an integer h >= 0, define
P_h(Z) = { sum_{e=0}^h z_e t^e : z_e in Z,
deg p <= h, p(t_i) in U_i for all i },
P_{-1}(Z) = {0},
k_h(Z) = dim P_h(Z) - dim P_{h-1}(Z),
E_h(Z;t) = { p(t) : p in P_h(Z) }.
(Here Z[xi] means "polynomials with coefficients in Z"; the condition
"p(t_i) in U_i" makes P_h(Z) a subspace.)
Step 1 (evaluation away from nodes). For t not in {t_1,...,t_m}, the
map ev_t : P_h(Z) -> Z, p |-> p(t), has kernel (xi - t) P_{h-1}(Z):
division by xi - t is well-defined because t is a scalar and the
constraint at t_i != t is preserved. Rank-nullity gives
dim E_h(Z; t) = k_h(Z) for every non-node t. [1]
Step 2 (evaluation at all nodes). The map
P_{m-1}(Z) -> product_{i=1}^m (U_i cap Z),
p |-> (p(t_1), ..., p(t_m))
is an isomorphism: injective because a degree <= m-1 vector polynomial
vanishing at the m distinct nodes t_i is zero (apply 6.6 coordinate by
coordinate), surjective because Lagrange interpolation
p(xi) = sum_i z_i * prod_{k != i} (xi - t_k)/(t_i - t_k)
lands in Z[xi] and satisfies p(t_i) = z_i. Hence
sum_{h=0}^{m-1} k_h(Z) = sum_{i=1}^m dim(U_i cap Z). [2]
Step 3 (degree filtration of W). Fix t* outside the node set. The
subspaces
E_0(W;t*) <= E_1(W;t*) <= ... <= E_{m-1}(W;t*)
are nested. Let ell_h = k_h(W) - k_{h-1}(W) >= 0. Choose polynomials
p_{h,1},...,p_{h,ell_h} in P_h(W) whose values at t* enlarge a basis
of E_{h-1}(W;t*) to a basis of E_h(W;t*). In fixed coordinates on W,
let M_h(t) be the matrix whose columns are all chosen polynomials
through stage h; it has r_h = k_h(W) columns. Choose an r_h-row
square minor Delta_h(t) with Delta_h(t*) != 0. Every column introduced
at stage e has degree <= e, so expanding the determinant:
deg Delta_h(t) <= sum_{e=0}^h e * ell_e. [3]
(If r_h = 0, take Delta_h = 1.)
Step 4 (rank loss at a node). For a node t_j, let pi_j : W -> W/V_j
be the quotient map. For t not a node, the kernel of pi_j on E_h(W;t)
contains E_h(V_j;t), so by [1],
dim pi_j(E_h(W;t)) <= k_h(W) - k_h(V_j).
Pass to t = t_j: every polynomial minor larger than that bound
vanishes at infinitely many nonnodes (hence is the zero polynomial),
so the bound still holds at t_j. But E_h(W;t_j) <= U_j and pi_j is
injective on U_j (since U_j cap V_j = {0}), so
dim E_h(W;t_j) <= k_h(W) - k_h(V_j). [4]
Step 5 (divisibility). The chosen columns of M_h(t_j) land in E_h(W;t_j),
and by [4] the square matrix defining Delta_h has nullity at least
k_h(V_j) at t_j. A square polynomial matrix with nullity >= q at t_j
has determinant divisible by (xi - t_j)^q: take q independent kernel
vectors at t_j, extend to a constant invertible column change, and note
that q transformed columns then vanish at t_j; each contributes a
factor of xi - t_j, while the column change rescales the determinant by
a nonzero constant. Applied at all m distinct nodes:
product_{j=1}^m (xi - t_j)^{k_h(V_j)} divides Delta_h(xi).
Delta_h is nonzero (Delta_h(t*) != 0), so
sum_{j=1}^m k_h(V_j) <= deg Delta_h <= sum_{e=0}^h e * ell_e.
[5]
Step 6 (assemble). Sum [5] over h = 0,...,m-1:
sum_{i,j} dim(U_i cap V_j)
= sum_{h=0}^{m-1} sum_j k_h(V_j) [by [2] with Z = V_j]
<= sum_{h=0}^{m-1} sum_{e=0}^h e * ell_e
= sum_{e=0}^{m-1} e (m - e) * ell_e
<= floor(m^2/4) * sum_{e=0}^{m-1} ell_e
= floor(m^2/4) * dim E_{m-1}(W; t*)
<= floor(m^2/4) * N. [by 6.6]
8. RANK SUMS OF DIFFERENCES
8.1 Corollary. Let X_1,...,X_m and Y_1,...,Y_m be d-by-d real matrices
with X_i - Y_i invertible for every i. Then
sum_{i!=k} rank(X_i - Y_k) >= 2 d_m d,
where d_m = floor(m/2) floor((m-1)/2) and the sum is over ORDERED pairs
of distinct indices.
8.2 Proof. Work in W = R^d + R^d (direct sum), dim W = 2d. Set
U_i = { (v, X_i v) : v in R^d },
V_j = { (v, Y_j v) : v in R^d }.
Then
U_i cap V_j = { (v, X_i v) : v in ker(X_i - Y_j) },
and the map v |-> (v, X_i v) identifies ker(X_i - Y_j) with U_i cap V_j,
so
dim(U_i cap V_j) = d - rank(X_i - Y_j).
For i = j, X_i - Y_i is invertible, so U_i cap V_i = {0}. Lemma 7.1
with N = 2d gives
sum_{i,j} (d - rank(X_i - Y_j)) <= floor(m^2/4) * 2d,
i.e., with S = sum_{i,j} rank(X_i - Y_j),
S >= d * (m^2 - 2 floor(m^2/4)).
The m diagonal terms each equal d, so the off-diagonal sum satisfies
sum_{i!=k} rank(X_i - Y_k) = S - m d
>= d * (m^2 - m - 2 floor(m^2/4)).
Direct expansion:
m = 2r: m^2 - m - 2 floor(m^2/4)
= 4r^2 - 2r - 2r^2 = 2r(r-1) = 2 d_m,
m = 2r+1: m^2 - m - 2 floor(m^2/4)
= (2r+1)^2 - (2r+1) - 2(r^2+r) = 2r^2 = 2 d_m.
Hence the off-diagonal sum is at least 2 d_m d. [QED]
8.3 A concrete check. Take m = 4, so d_m = floor(4/2) floor(3/2) = 2.
For any 4 pairs of d-by-d matrices (X_i, Y_i) with X_i - Y_i invertible,
the corollary guarantees
sum_{i != k} rank(X_i - Y_k) >= 2 d_m d = 4d,
over the 12 off-diagonal ordered pairs. In the crossing application
(Section 16) each rank(R_ik) is bounded by the crossing count c_ik of
stars i and k, and sum_{i != k} c_ik = 2 c(D). The corollary gives
4d <= 2 c(D), so c(D) >= 2d = d_4 d_n.
This matches the odd-case theorem cr(K_{4,n}) = d_4 d_n.
==============================================================================
PART V GEOMETRIC MACHINERY
==============================================================================
9. SIGNED INTERSECTIONS
9.1 Setting. Fix a minimum drawing D of K_{m,n}, normalized as in
Section 18.
9.2 Orient every edge a_i b_p FROM a_i TO b_p. Call this the fixed
orientation.
9.3 Signed crossing count. For oriented edges e,f, let I(e,f) be the
sum over interior crossings x of e with f of
sign( det(u_x, v_x) ),
where u_x and v_x are the tangents of e and f at x, both directed by
the fixed orientation. Conventions:
I(e,e) = 0,
I(e,f) = -I(f,e).
9.4 Spoke order at a vertex. At a vertex v, choose a "cut" between
two consecutive edges leaving v, then list all edges at v counter-
clockwise from that cut. Define
T_v(e,f) = +1 if e precedes f in that list,
-1 if f precedes e,
0 if e = f,
and
sigma_{v,e} = +1 if e is oriented OUT of v,
-1 if e is oriented INTO v.
For the fixed orientations, sigma = +1 at every a_i and sigma = -1 at
every b_p. Hence sigma_{v,e} sigma_{v,f} = +1 whenever e and f share
the vertex v.
9.5 The matrix J. For any two edges e,f of K_{m,n}, define
J(e,f) = I(e,f)
+ (1/2) * sum over common endpoints v of e,f
sigma_{v,e} sigma_{v,f} T_v(e,f).
Reading off the cases:
e = f: J(e,e) = 0.
share a_i only: J(e,f) = I(e,f) + (1/2) T_{a_i}(e,f).
share b_p only: J(e,f) = I(e,f) + (1/2) T_{b_p}(e,f).
share nothing: J(e,f) = I(e,f).
Because I and T are antisymmetric, J is antisymmetric: J(e,f) = -J(f,e).
9.6 Blocks. Number the edges as e_{ip} = a_i b_p. Define
J^{ik}(p,q) = J(e_{ip}, e_{kq}).
Each J^{ik} is n x n; J is mn x mn, arranged in an m-by-m grid of
n-by-n blocks.
9.7 Diagonal blocks are spoke orders. For p != q,
J^{ii}(p,q) = I(e_{ip}, e_{iq}) + (1/2) T_{a_i}(e_{ip}, e_{iq}).
The first term is zero (adjacent edges at a_i do not cross). So
J^{ii}(p,q) = (1/2) T_{a_i}(e_{ip}, e_{iq}).
This is exactly HALF the comparison-sign matrix of the spoke order at
a_i, i.e.,
J^{ii} = S_prec,
S_prec(p,q) = +1/2 if p precedes q,
-1/2 if q precedes p,
0 if p = q.
That is the S_prec whose invertibility the detector will need.
10. THE CHORD FORMULA
10.1 Two oriented chords of a disk. Let C and E be two oriented
straight chords of a round disk with four distinct endpoints. Define
endpoint coefficients
eps_C(u) = -1 if u = start(C),
+1 if u = end(C),
0 otherwise,
and similarly eps_E.
10.2 The chord formula. Place a "cut" in the boundary circle away
from all four endpoints. For two boundary points u, w, let T(u,w) be
+1 if u precedes w counterclockwise from the cut and -1 if w precedes
u. Then the signed intersection of C and E equals
I(C,E) = (1/2) sum_{u in {start C, end C}}
sum_{w in {start E, end E}}
eps_C(u) eps_E(w) T(u,w).
10.3 Cut invariance. Moving the cut past one boundary point x shifts
every T-value by a step function whose change contributes a constant
multiple of sum_w eps_E(w) = (-1) + (+1) = 0. Same when the cut passes
an endpoint of E. So the right-hand side does not depend on the cut.
10.4 Evaluate. Place the cut just before start(C). Then
- For u = start(C), T(start C, w) = +1 for both w. The
contribution is (1/2)(-1)(eps_E(start E) + eps_E(end E)) = 0.
- For u = end(C), T(end C, w) = -1 for w on the open CCW arc
from start(C) to end(C), and +1 for w on the complementary arc.
Let A be the sum of eps_E(w) over the first arc and B over the
complementary arc. Then A + B = 0 and the contribution is
(1/2)(+1)(-A + B) = -A.
Hence
I(C,E) = - sum_{w on the open CCW arc from start C to end C}
eps_E(w).
10.5 What the formula says.
Nonalternating: both endpoints of E lie on the same arc. The
sum over the arc is either eps_E + eps_E = 0 (both on) or 0
(both off), so I = 0.
Alternating: one endpoint on each arc. The sum picks up exactly
one eps_E value, giving +1 or -1 depending on orientation. This
matches the geometric sign of a transverse crossing.
10.6 Why we need it. When a shared vertex disk is replaced by chords,
the chord formula tells us the local contribution of the disk to a
signed intersection. The factor 1/2 in J comes from averaging the two
possible "shifts" of a track (left and right), as in Section 11.
11. THE CYCLE-PAIRING LEMMA
11.1 Cycle vectors. A CYCLE is a closed walk visiting no vertex
twice except at its start. Given an oriented cycle of K_{m,n}, its
CYCLE VECTOR z in R^{E(K_{m,n})} has
z_e = +1 if e is traversed with the fixed orientation,
-1 if against,
0 if unused.
11.2 Lemma (cycle pairing). For any two oriented simple cycles of
K_{m,n} with cycle vectors z, y,
z^T J y = 0.
11.3 Proof. Let the two cycles be C (using z) and D (using y).
Step 1. Replace C by a closed polygonal walk gamma: place small round
vertex disks centered at the vertices of C, all disjoint, meeting only
the drawing's straight spokes; inside each disk replace the two
incident spokes by the chord joining their boundary endpoints. Outside
the disks keep the original tracks. gamma is a closed polygonal walk
(possibly with self-intersections), carrying signed weights z.
Step 2. Replace D by two nearby walks eta_+ (shifted left) and
eta_- (shifted right) relative to the fixed orientation. Inside small
disks centered at crossings and bends of D, connect the shifted ends by
short arcs; choose shifts tiny enough that
(i) at each crossing disk, shifted tracks meet the corresponding
unshifted tracks with the same crossing sign as before;
(ii) at each shared vertex disk, the two shifted copies of a
common spoke's boundary endpoint lie on OPPOSITE sides of
the unshifted endpoint, so their T-signs cancel on average.
Then eta_+ and eta_- are closed polygonal walks carrying weights y.
Step 3. Two closed polygonal walks with only transverse intersections
have total signed intersection zero. Reason: pick a point o outside
everything, cone the first walk to o, and note each triangle [o, u, w]
bounds a region, so every entrance of the second walk to that region is
matched by an exit with the opposite sign - the total is zero. Summing
over all triangle boundaries, the extra cone segments [o,u] cancel in
pairs, leaving exactly the first walk. The argument counts oriented
traversals and so works for non-simple walks. Hence signed intersection
of gamma with eta_+ equals zero, and likewise for eta_-.
Step 4. For either eta, the signed intersection of gamma with eta
splits into contributions:
exterior part + vertex-disk parts = 0.
The exterior part is the sum over pairs of edges (each from a cycle) of
z_e y_f I(e,f), equal to z^T I y; it does not depend on the choice of
shift. At a shared vertex v, the local contribution is
(1/2) sum_{e,f at v} sigma_{v,e} sigma_{v,f} T_v(e,f) z_e y_f,
the 1/2 being the average of the two shifts. When e = f, the two
shifted endpoints sit on opposite sides of the unshifted endpoint, so
their T-signs are opposite and average to zero, matching the convention
T_v(e,e) = 0.
Summing:
0 = z^T I y + (1/2) sum_v sum_{e,f at v}
sigma sigma T z_e y_f
= z^T J y. [QED]
11.4 The 1/2 in the definition of J is exactly what averaging over
left and right shifts produces; the antisymmetric convention
T_v(e,e) = 0 forces the two shifts to cancel at diagonal spokes.
12. THE ADDITIVE BLOCK RELATION
12.1 Additive matrices. A matrix H in R^{n x n} is ADDITIVE (row
plus column) if there exist vectors r, c with H(p,q) = r_p + c_q for
all p, q. Equivalently, for all p, p', q, q':
H(p,q) - H(p,q') - H(p',q) + H(p',q') = 0.
Proof: (=>) immediate expansion. (<=) fix p_0 = q_0 = 1 and set
r_p = H(p,1) and c_q = H(1,q) - H(1,1).
12.2 Lemma (additive block relation). For all 1 <= i,k <= m, the
n x n matrix
H(i,k) = J^{ik} - J^{i1} - J^{1k} + J^{11}
is additive.
12.3 Proof. Fix i,k. If i = 1 then H(1,k) = 0, additive. Same if
k = 1. Assume i,k >= 2. If p = p' or q = q', the alternating sum
vanishes trivially. Assume p != p' and q != q'.
Build the 4-cycle z on {ip, 1p, 1p', ip'}:
cycle: a_i -> b_p -> a_1 -> b_p' -> a_i.
Traversals vs fixed orientations:
ip: a_i -> b_p, matches; z_{ip} = +1
1p: b_p -> a_1, against a_1 -> b_p; z_{1p} = -1
1p': a_1 -> b_p', matches; z_{1p'} = +1
ip': b_p' -> a_i, against a_i -> b_p'; z_{ip'} = -1
z = 0 elsewhere.
Similarly the 4-cycle y on {kq, 1q, 1q', kq'} gives
y_{kq} = +1, y_{1q} = -1, y_{1q'} = +1, y_{kq'} = -1,
y = 0 elsewhere.
By Lemma 11.2, z^T J y = 0. Expanding all 16 nonzero products and
regrouping:
z^T J y
= J(ip,kq) - J(ip,1q) - J(ip,kq') + J(ip,1q')
- J(1p,kq) + J(1p,1q) + J(1p,kq') - J(1p,1q')
+ J(1p',kq) - J(1p',1q) - J(1p',kq') + J(1p',1q')
- J(ip',kq) + J(ip',1q) + J(ip',kq') - J(ip',1q')
= H(p,q) - H(p,q') - H(p',q) + H(p',q').
Therefore H satisfies the characterizing four-term identity of 12.1,
so H is additive. [QED]
12.4 Consequence (differences form). Let Phi be ANY linear map on
n x n matrices that annihilates every additive matrix. Applying Phi
to 12.2:
Phi(J^{ik}) - Phi(J^{i1}) - Phi(J^{1k}) + Phi(J^{11}) = 0,
i.e., with
R_ik = Phi(J^{ik}), X_i = R_i1, Y_k = R_11 - R_1k,
for all i,k:
R_ik = X_i - Y_k.
In particular for i = k,
X_i - Y_i = R_ii = Phi(J^{ii}) = Phi(S_prec at a_i).
12.5 Goals for the detector Phi. For odd n = 2s+1 and d = s^2, we
need a linear map Phi : R^{n x n} -> R^{d x d} with:
(i) Phi annihilates every additive matrix and every diagonal
matrix.
(ii) Phi(E_pq) has rank <= 1 for every standard matrix E_pq.
(iii) Phi(S_prec) is invertible for every strict total order prec
on {1,...,n}.
Goals (i)-(ii) turn the block relations into a rank bound; goal (iii)
gives the diagonal invertibility that the rank-sum corollary needs.
Sections 13-15 build such a Phi.
==============================================================================
PART VI THE RANK DETECTOR
==============================================================================
13. LAGRANGE INTERPOLATION AND BARYCENTRIC WEIGHTS
13.1 Lagrange. Given n distinct reals x_1,...,x_n and arbitrary
values y_1,...,y_n, there is a unique polynomial P of degree <= n-1
with P(x_i) = y_i. It is
P(t) = sum_{i=1}^n y_i L_i(t),
L_i(t) = prod_{k != i} (t - x_k) / (x_i - x_k).
13.2 Barycentric form. Let F(t) = prod_{p=1}^n (t - x_p). Then
F'(x_i) = prod_{k != i} (x_i - x_k), so
L_i(t) = F(t) / ((t - x_i) F'(x_i)).
The numbers w_i = 1 / F'(x_i) are the BARYCENTRIC WEIGHTS. They are
nonzero because the nodes x_i are distinct.
13.3 Vanishing identity. If deg A <= n-2, then
sum_{i=1}^n A(x_i) * w_i = 0.
Proof: By Lagrange, A(t) = sum_i A(x_i) L_i(t) as polynomials. Each
L_i has leading coefficient w_i. The coefficient of t^{n-1} on the
left side is 0 (since deg A <= n-2 < n-1); on the right it is
sum_i A(x_i) w_i. Comparing gives the claim.
14. TWO-TRIANGLE INTERPOLATION
14.1 Setting. Fix n = 2s+1 distinct reals x_1,...,x_n. Consider
bivariate polynomials P(u,v) of BIDEGREE <= (s-1, s-1) (i.e., deg_u <=
s-1 and deg_v <= s-1). They form a real vector space of dimension
s^2 = d, with monomial basis
{ u^a v^b : 0 <= a, b <= s-1 }.
For each pair (p,q), define the evaluation vector h_pq in R^{s^2} by
h_pq(a,b) = x_p^a * x_q^b ,
so that P(x_p,x_q) = "c . h_pq" where c is the coefficient vector.
14.2 The two-triangle pattern.
Q_s = { (p,q) : 1 <= q < p <= s+1 }
u { (p,q) : s+1 < p < q <= 2s+1 }.
Its size:
|Q_s| = s(s+1)/2 + s(s-1)/2 = s^2 = d.
For s=3 (n=7), with rows p and columns q, X = in Q_s:
p vs q 1 2 3 4 5 6 7
1 . . . . . . .
2 X . . . . . .
3 X X . . . . .
4 X X X . . . .
5 . . . . . X X
6 . . . . . . X
7 . . . . . . .
Row 4 (= s+1) is the last row of the first (lower-left) triangle; it
is exactly the row eliminated in Step A below. Column 1 is the
corresponding column eliminated in Step B.
14.3 Lemma (two-triangle interpolation). If P has bidegree <= (s-1,s-1)
and vanishes at every (x_p, x_q) with (p,q) in Q_s, then P is the zero
polynomial. Equivalently, { h_pq : (p,q) in Q_s } is a basis of R^{s^2}.
14.4 Proof. Both sides have dimension s^2, so it suffices to prove
injectivity. Induction on s.
Base case, s=1: P is constant, Q_1 = {(2,1)}, so P(x_2,x_1) = 0 gives
P = 0.
Induction step (s >= 2).
Step A: eliminate u - x_{s+1}. The points (s+1, 1), (s+1, 2), ...,
(s+1, s) all lie in Q_s (q < p = s+1, so q <= s). Hence
P(x_{s+1}, x_q) = 0 for q = 1,...,s. The polynomial P(x_{s+1}, v) has
degree <= s-1 in v and s distinct roots, so it is identically zero.
Hence
P(u,v) = (u - x_{s+1}) * P_1(u,v),
deg_u P_1 <= s-2, deg_v P_1 <= s-1.
Step B: eliminate v - x_1. The points (p, 1) for p = 2,...,s all lie
in Q_s (1 < p <= s < s+1). So P(x_p, x_1) = 0 for p = 2,...,s. Since
x_p != x_{s+1} for p <= s, the factor (x_p - x_{s+1}) is nonzero, so
P_1(x_p, x_1) = 0 for p = 2,...,s. The polynomial P_1(u, x_1) has
degree <= s-2 in u and s-1 distinct roots, so it is identically zero.
Hence
P_1(u,v) = (v - x_1) * R(u,v),
deg_u R <= s-2, deg_v R <= s-2,
and
P(u,v) = (u - x_{s+1}) (v - x_1) R(u,v).
Step C: what remains of Q_s. Columns and rows already used:
- step A used every point with p = s+1;
- step B used every point with q = 1.
What is left of Q_s:
A = { (p,q) : 2 <= q < p <= s }
B = { (p,q) : s+1 < p < q <= 2s+1 }.
At every point in A u B both factors (x_p - x_{s+1}) and (x_q - x_1)
are nonzero, so R vanishes at all (x_p, x_q) with (p,q) in A u B.
Step D: smaller Q_{s-1}. Define a tuple of 2s-1 distinct nodes
(y_1, ..., y_{2s-1})
= (x_{s+2}, x_{s+3}, ..., x_{2s+1}, x_2, x_3, ..., x_s),
i.e., y_r = x_{s+1+r} for r = 1,...,s and y_r = x_{r-s+1} for
r = s+1,...,2s-1. (This is exactly x_1,...,x_{2s+1} with x_1 and
x_{s+1} removed.) Define S(u,v) = R(v,u). Then S has bidegree
<= (s-2, s-2) = ((s-1)-1, (s-1)-1). We claim S vanishes on Q_{s-1} for
the y-tuple.
Case 1 (first triangle of Q_{s-1}): 1 <= w < r <= s.
y_r = x_{s+1+r}, y_w = x_{s+1+w},
S(y_r, y_w) = R(y_w, y_r) = R(x_{s+1+w}, x_{s+1+r}).
Row index s+1+w, column index s+1+r. Since 1 <= w < r <= s,
s+1 < s+1+w < s+1+r <= 2s+1,
so (s+1+w, s+1+r) lies in B, where R vanishes.
Case 2 (second triangle of Q_{s-1}): s < r < w <= 2s-1.
y_r = x_{r-s+1}, y_w = x_{w-s+1},
S(y_r, y_w) = R(y_w, y_r) = R(x_{w-s+1}, x_{r-s+1}).
Row index w-s+1, column index r-s+1. Since r < w and r >= s+1,
2 <= r-s+1 < w-s+1 <= s,
so (w-s+1, r-s+1) lies in A, where R vanishes.
By induction, S = 0. Then R = 0, then P = 0. [QED]
15. THE RANK DETECTOR
15.1 Goal. For odd n = 2s+1, build Phi : R^{n x n} -> R^{s^2 x s^2}
satisfying (i)-(iii) of Section 12.5.
15.2 Setup. Fix nodes x_1 < x_2 < ... < x_n. Let
F(t) = prod_p(t - x_p), w_p = 1 / F'(x_p).
15.3 Blocks. For each (p,q) in {1,...,n}^2, recall h_pq from 14.1 and
set
B_pq = (x_p - x_q) * w_p * w_q * (h_pq h_pq^T),
where h_pq h_pq^T is the OUTER PRODUCT with entries
(h_pq h_pq^T)[(a,b), (a',b')] = x_p^{a+a'} * x_q^{b+b'}.
15.4 Definition. Define Phi by
Phi(H) = sum_{p,q=1}^n H(p,q) * B_pq.
Phi is linear in H, by construction.
15.5 Property (ii). Phi(E_pq) = B_pq. Since h_pq != 0 (its (0,0)
coordinate is 1) and (x_p - x_q) w_p w_q is a nonzero scalar when
p != q, B_pq has rank exactly 1 for p != q, and B_pp = 0 (the
prefactor x_p - x_p vanishes).
15.6 Property (i). Phi(I_n) = sum_p B_pp = 0, so Phi annihilates
every diagonal matrix. For a row-constant matrix H(p,q) = r_p,
Phi(H) = sum_p r_p * (sum_q B_pq).
The (a,b; a',b') entry of sum_q B_pq is
sum_q (x_p - x_q) w_p w_q x_p^{a+a'} x_q^{b+b'}
= w_p x_p^{a+a'} * [ x_p * sum_q w_q x_q^{b+b'}
- sum_q w_q x_q^{1+b+b'} ].
Since b + b' <= 2s-2 = n-3 < n-2 and 1 + b + b' <= 2s-1 = n-2, both
inner sums vanish by the vanishing identity 13.3. So sum_q B_pq = 0
for each p, and Phi annihilates row-constant matrices. Symmetrically,
sum_p B_pq = 0 for each q, so Phi annihilates column-constant matrices.
Any additive matrix is row-constant plus column-constant; hence
Phi(H) = 0. This proves (i).
15.7 Property (iii). Fix the natural order 1 < 2 < ... < n. Let
H(p,q) = 1 if q < p, else 0. Then
S_nat = (1/2) 1 1^T - H - (1/2) I_n,
where 1 = all-ones column. Check:
p < q: 1/2 - 0 - 0 = 1/2.
p > q: 1/2 - 1 - 0 = -1/2.
p = q: 1/2 - 0 - 1/2 = 0.
Applying Phi and using (i):
Phi(S_nat) = (1/2) Phi(1 1^T) - Phi(H) - (1/2) Phi(I_n)
= -Phi(H).
Step A. Define H' by
H'(p,q) = H(p,q) for p <= s+1,
= H(p,q) - 1 for p > s+1.
Then H - H' is row-constant (value 0 for p <= s+1, 1 for p > s+1), so
by (i) Phi(H) = Phi(H').
Step B. Off the diagonal, H' equals
+1 on Q_s-first-triangle { q < p <= s+1 },
0 elsewhere above the diagonal in rows p <= s+1,
0 below the diagonal in rows p > s+1,
-1 on Q_s-second-triangle { s+1 < p < q }.
On the diagonal H' may be nonzero; Phi kills B_pp = 0, so the diagonal
does not contribute. So the off-diagonal support of H' is exactly Q_s,
with sign +1 on the first triangle and -1 on the second.
Step C. Group the Q_s pairs in any order, and let A_Q be the s^2 x s^2
matrix whose columns are h_pq for (p,q) in Q_s. Let D_Q be the
diagonal matrix
D_Q[(p,q),(p,q)] = H'(p,q) (x_p - x_q) w_p w_q
for (p,q) in Q_s. Then
Phi(H') = A_Q * D_Q * A_Q^T.
Step D. A_Q is invertible by Lemma 14.3, and every diagonal entry of
D_Q is nonzero: H'(p,q) = +-1 on Q_s, x_p != x_q, w_p and w_q nonzero.
Hence Phi(H') is invertible, and so is Phi(S_nat) = -Phi(H').
Step E (arbitrary order). Let prec be any strict total order on
{1,...,n}. Choose a bijection pi with pi(1) prec pi(2) prec ...
prec pi(n). Build Phi' with nodes x'_r = x_{pi(r)}. Step D applies to
Phi', so Phi'(S_nat) is invertible. Since
B'_{rw} = (x'_r - x'_w) w'_r w'_w h'_{rw} h'^T_{rw}
= B_{pi(r), pi(w)},
and since r < w iff pi(r) prec pi(w), we have
S_nat(r,w) = S_prec(pi(r), pi(w)) for all r,w.
Therefore
Phi'(S_nat) = sum_{r,w} S_nat(r,w) B'_{rw}
= sum_{r,w} S_prec(pi(r),pi(w)) B_{pi(r),pi(w)}
= sum_{p,q} S_prec(p,q) B_{pq}
= Phi(S_prec).
Hence Phi(S_prec) = Phi'(S_nat) is invertible.
This completes the construction. The map Phi : R^{n x n} -> R^{s^2 x s^2}
satisfies properties (i)-(iii) of Section 12.5.
==============================================================================
PART VII THE ODD CASE
==============================================================================
16. THE ODD CASE OF THE LOWER BOUND
16.1 Setup. Let n = 2s+1 >= 3, so d_n = s^2 =: d. Let m >= 3 (else
d_m = 0 and the bound is trivial). Take a minimum drawing D of
K_{m,n}, normalized as in Section 18. Build the block matrix J
(Section 9). Use the detector Phi from Section 15, so Phi maps n x n
matrices to s^2 x s^2 = d x d matrices.
16.2 Definitions.
R_ik = Phi(J^{ik}) (a d x d matrix),
X_i = R_i1,
Y_k = R_11 - R_1k.
16.3 Difference form. By 12.4 (additivity of H(i,k) and annihilation
by Phi):
R_ik = X_i - Y_k for all 1 <= i, k <= m.
16.4 Diagonal invertibility. Taking k = i:
X_i - Y_i = R_ii = Phi(J^{ii}) = Phi(S_prec of a_i).
By 15.7 (property (iii)), Phi(S_prec) is invertible for every strict
total order. Hence X_i - Y_i is invertible for every i.
16.5 Off-diagonal rank bound. For i != k,
rank R_ik <= c_ik,
where c_ik is the number of crossing POINTS between edges of the i-th
and k-th stars.
Proof. R_ik = sum_{p,q} J^{ik}(p,q) B_pq. Each B_pq has rank <= 1 (by
15.5), so by subadditivity of rank,
rank R_ik <= #{ (p,q) : p != q, J^{ik}(p,q) != 0 }.
(B_pp = 0 kills the diagonal entries.) For i != k, the entries at
p != q are J^{ik}(p,q) = I(e_{ip}, e_{kq}) (edges with distinct
endpoints). Any nonzero I-value requires at least one crossing of
e_{ip} with e_{kq}, and each crossing point contributes to exactly one
(p,q). So the count is at most c_ik.
16.6 Apply rank-sum corollary. Section 8, applied to the matrices
X_1,...,X_m, Y_1,...,Y_m (all d x d, with X_i - Y_i invertible by
16.4), gives
sum_{i != k} rank(X_i - Y_k) >= 2 d_m d = 2 d_m d_n.
Combining with 16.5:
2 d_m d_n <= sum_{i != k} rank(R_ik)
<= sum_{i != k} c_ik
= 2 c(D).
The final equality: every crossing of D joins edges with distinct
b-endpoints (adjacency normalization), so it is counted exactly once in
c_ik and exactly once in c_ki. Hence the double sum is 2 c(D).
16.7 Conclusion. c(D) >= d_m d_n. Since D was an arbitrary minimum
drawing, cr(K_{m,n}) >= d_m d_n. Together with the upper bound
cr(K_{m,n}) <= d_m d_n:
cr(K_{m,n}) = d_m d_n for odd n >= 3.
For m <= 2 the upper bound already gives cr = 0 = d_m d_n.
==============================================================================
PART VIII THE EVEN CASE
==============================================================================
17. THE EVEN CASE
17.1 Identity. For n = 2s >= 4,
n d_{n-1} / (n-2) = d_n.
Check: d_{n-1} = d_{2s-1} = (s-1)^2, d_n = d_{2s} = s(s-1). Then
(2s)(s-1)^2 / (2s-2) = s(s-1) = d_n.
17.2 Vertex deletion. Let n = 2s >= 4. Take a minimum drawing D of
K_{m,n}, normalized. For each p = 1,...,n let D_p be D with the vertex
b_p and its m incident edges deleted. D_p is a drawing of K_{m,n-1}
(n-1 odd). By the odd case,
c(D_p) >= d_m d_{n-1} for every p.
17.3 Double count. A crossing of D lies between two edges e_{ip} and
e_{kq} with i != k and p != q (adjacency normalization). It involves
exactly two b-vertices, b_p and b_q, so it survives in D_{p'} iff
p' not in {p,q}: there are n-2 such p'. Therefore
sum_{p=1}^n c(D_p) = (n-2) c(D).
17.4 Combine.
(n-2) c(D) = sum_p c(D_p) >= n d_m d_{n-1} = (n-2) d_m d_n,
using 17.1 in the last step. Divide by n-2:
c(D) >= d_m d_n.
Combined with the upper bound:
cr(K_{m,n}) = d_m d_n for every even n >= 4.
Edge cases n <= 2 or m <= 2: the upper bound gives cr = 0 = d_m d_n.
==============================================================================
PART IX NORMALIZING A DRAWING
==============================================================================
18. DRAWING NORMALIZATION
18.1 Lemma. Every admissible continuous-arc drawing of a finite simple
graph can be replaced by a polygonal drawing with
(a) at most the same number of crossing points,
(b) edges straight near every vertex and every crossing,
(c) no crossings between edges sharing an endpoint,
(d) no triple crossings, tangencies, or shared arcs.
All arguments in Parts V-VII assume such a normalized drawing.
18.2 Proof. Call the vertices and crossings of the drawing its MARKS
(finitely many). Parameterize each edge e as a continuous injective
arc gamma_e : [0,1] -> R^2.
Step 1 (isolate marks). On each edge, choose pairwise disjoint
parameter neighborhoods of its marked parameters (one-sided at 0 and
1). For each mark w and edge e: the image of the compact parameter set
outside its w-neighborhood is at positive distance from w (because it
avoids w); an edge not incident to w has its whole compact image at
positive distance from w. Since there are finitely many (e,w), there
exist pairwise disjoint closed round disks D_w, centered at the marks,
such that
- every visit of any edge to D_w lies in its w-neighborhood;
- every edge not incident to w avoids D_w entirely.
Step 2 (reconstruct exterior pieces). For an interior mark on e,
delete the parameter interval between the FIRST and the LAST visit to
D_w (this removes the intervening excursions too). For a starting or
terminal endpoint, use a one-sided neighborhood. These deleted
intervals are pairwise disjoint along e. The retained pieces are
compact arcs, each with interior in the open set
Omega = R^2 minus (union of closed D_w).
They are pairwise disjoint, with distinct endpoints (every would-be
intersection was a mark and is now off-limits).
Now replace each retained piece by a polygonal arc inside Omega.
Choose pairwise disjoint open neighborhoods U_P of the retained pieces,
contained in Omega. A standard topological fact: a continuous path
with compact image in an open set in the plane can be replaced, with
the same endpoints, by a polygonal path in that open set. Pick short
straight "spurs" from each disk boundary into the collar U_P at the
endpoint, then connect the spur tip to a nearby interior point of the
piece inside U_P, and replace the piece's interior between those points
by a polygonal path in U_P. Join everything. The result is a family
of polygonal arcs in Omega, each meeting disks only at its boundary
endpoints, with interiors pairwise disjoint.
Step 3 (fill disks). In a crossing disk D_w, join each of the two
pairs of boundary endpoints by a straight chord. The four endpoints
are distinct, no straight line contains four points of a circle, so the
two chords meet in at most one point, and any meeting is transverse
and interior. In a vertex disk D_w, choose a new vertex point not on
any line through two boundary endpoints, and connect every boundary
endpoint to it by a straight spoke; spokes meet only at the vertex.
Assemble spokes, chords, and exterior polygonal pieces in the original
edge order. Each resulting edge is a simple path: exterior pieces
disjoint, at most one chord or spoke per disk, interior avoids all
vertices. Every inter-edge crossing of the final drawing lies inside
an original crossing disk, is transverse, and is unique in its disk
(no triples). So the drawing is admissible, polygonal, straight near
every vertex and crossing, and has no more crossings than the original.
Step 4 (remove adjacent-edge crossings). Suppose two polygonal edges
e = vu and f = vw share vertex v and cross at an interior point x
(simple graph: u != w). Choose a small round disk about x meeting
only the two straight strands of the crossing; contain no other mark or
bend. Swap the portions of e and f from v up to this disk, and
reconnect the swapped prefixes to the original suffixes with two
disjoint chords inside the disk, pairing adjacent boundary endpoints.
Inside the disk the crossing at x vanishes; outside the disk every
old open track is used exactly once by the two new walks. The result
is two polygonal WALKS (possibly with self-intersections).
Subdivide these walks at all remaining crossings and bends, then
repeatedly delete any closed sub-walk between two occurrences of the
same subdivision vertex. Each deletion shortens a finite walk, so the
process terminates, yielding simple polygonal paths. One checks
admissibility is preserved:
- a remaining crossing of two tracks that end up in different new
walks is a straight-through passage counted exactly once;
- a remaining crossing of two tracks that end up in the same new
walk, or any loop deletion that creates a turn, occurs at a
point where no other edge is present (the original had no
triples or shared arcs), so no admissibility rule is violated;
- vertex and endpoint contacts are as before.
Repeat Step 4 as long as an adjacent-edge crossing remains. Each
iteration decreases the (finite) crossing count by at least 1, so the
process terminates. Additionally, nudge the vertex positions or the
straight stretches by a tiny generic amount to eliminate any residual
triple crossings or tangencies.
18.3 Result. Any admissible drawing can be replaced by an admissible
polygonal drawing satisfying (a)-(d). In particular, any MINIMUM
drawing can be normalized without loss of optimality.
==============================================================================
PART X FURTHER READING
==============================================================================
19. FURTHER READING
19.1 Crossing-number background.
J. Pach and G. Toth, "Which crossing number is it anyway?",
JCTB 80 (2000), 225-246.
P. Erdos and R. K. Guy, "Crossing number problems",
Amer. Math. Monthly 80 (1973), 52-58.
19.2 The Zarankiewicz problem.
P. Turan, "A note of welcome", J. Graph Theory 1 (1977), 7-9.
(origin of the brick-factory question)
C. Zarankiewicz, Fund. Math. 41 (1955), 137-145.
(upper-bound drawing; incomplete optimality claim)
D. J. Kleitman, "The crossing number of K_{5,n}",
J. Combin. Theory 9 (1970), 315-323.
(exact for m <= 6; the vertex-deletion argument)
D. R. Woodall, "Cyclic-order graphs and Zarankiewicz's
crossing-number conjecture", J. Graph Theory 17 (1993), 657-671.
(verified K_{7,7} = 81)
E. de Klerk, J. Maharry, D. V. Pasechnik, R. B. Richter, G. Salazar,
"Improved bounds for the crossing numbers of K_{m,n} and K_n",
SIAM J. Discrete Math. 20 (2006), 189-202.
D. Brosch and S. C. Polak, "New lower bounds on crossing numbers of
K_{m,n} from semidefinite programming", Math. Programming 207
(2024), 693-715.
J. Balogh, B. Lidicky, S. Norin, F. Pfender, G. Salazar, S. Spiro,
"Crossing numbers of complete bipartite graphs", Procedia Comput.
Sci. 223 (2023), 78-87. (best prior lower bound:
cr(K_{n,n}) >= 0.9118 d_n^2 + o(n^4))
19.3 Tools used here.
J.-P. Berrut and L. N. Trefethen, "Barycentric Lagrange
interpolation", SIAM Review 46 (2004), 501-517.
(barycentric weights);
V. Guruswami and S. Kopparty, "Explicit subspace designs",
Combinatorica 36 (2016), 161-185
(related determinant-multiplicity technique).
19.4 Logical flow in one picture.
A drawing D of K_{m,n}
|
| normalize (Section 18)
v
Normalized minimum drawing D
|
| build J (Sections 9-12)
v
Antisymmetric block matrix J = (J^{ik})
|
| apply Phi (Sections 13-15)
v
Matrices R_ik = X_i - Y_k,
X_i - Y_i invertible,
rank(R_ik) <= c_ik
|
| rank-sum inequality (Section 8)
v
2 d_m d_n <= 2 c(D), hence c(D) >= d_m d_n.
|
| even n: vertex deletion (Section 17)
v
d_m d_n <= c(D) for all m,n.
==============
Equality follows from the upper bound (Section 4).
19.5 Sanity checks on d_m d_n. The values:
m=n=1: 0 m=n=2: 0
m=n=3: 1 m=n=4: 4
m=n=5: 16 m=n=6: 36
m=n=7: 81 m=n=8: 144
For m=n=3 this is 1, matching the geometric lower bound cr(K_{3,3}) >= 1
(K_{3,3} is nonplanar). For m=n=4 this is 4, matching Kleitman's 1970
computation. For m=n=7 this is 81, matching Woodall's 1993 computer
verification. All entries grow like m^2 n^2 / 16, consistent with the
balanced-axis construction of Section 4.
END.