Results on drawings, signed crossings, interpolation and the crossing numbers of complete graphs, with their assumptions

The course proves the statements below; each link leads to the statement with its assumptions and its proof. The lessons are self-checked by the writing AI; independent mathematical review is not complete.

• Drawings and the crossing number — Definition 1.1. Vertices at distinct points, edges as simple arcs whose interiors avoid the vertices and meet in finitely many proper crossings of two edges; cr(G) is the least number of crossing points.
• Zarankiewicz's formula (OpenAI) — Theorem A. cr(K_{m,n}) = d_m d_n with d_r = floor(r/2) floor((r-1)/2). Proved in the lesson The Zarankiewicz formula. No hypothesis.
• The Harary-Hill formula (OpenAI) — Theorem B. cr(K_n) = Z(n) = d_n d_(n-2)/4 for n >= 3. Proved in the lesson Two-page drawings and the Harary-Hill formula. No hypothesis.
• Polynomials vanishing on open sets — Lemma 3.1. A real polynomial vanishing on a nonempty open set is zero, so finitely many nonzero polynomials have a common nonzero point in every nonempty open set. No hypothesis.
• Zarankiewicz's drawing — Proposition 4.1. K_{m,n} has a straight-line drawing with exactly d_m d_n crossing points, so cr(K_{m,n}) <= d_m d_n. No hypothesis.
• Normal drawings — Definition 1.1. Polygonal, straight near every vertex and crossing point, and without crossings of edges with a common endpoint.
• Normalization (OpenAI) — Theorem 1.2. Every drawing can be replaced by a normal drawing with no more crossing points; cr(G) is attained by a normal drawing. No hypothesis.
• Polygonal paths in open sets — Lemma 2.1. A continuous path in an open subset of the plane can be replaced by a polygonal walk in it with the same ends. No hypothesis.
• Removing loops — Lemma 2.2. A polygonal walk between distinct points contains a polygonal arc between them. No hypothesis.
• From arcs to polygons — Proposition 3.1. Every drawing has a polygonal drawing with no more crossing points that is straight near its vertices and crossing points. No hypothesis.
• One exchange — Proposition 4.1. If two edges with a common endpoint cross, exchanging their initial parts and removing loops gives a drawing with fewer crossing points. No hypothesis.
• Four endpoints — Corollary 4.2. In a normal drawing every crossing point lies on two edges with four distinct endpoints. No hypothesis.
• Simple cycles span the cycle space — Lemma 1.1. The cycle space of a graph is spanned by the signed edge vectors of oriented simple cycles. No hypothesis.
• The form J — Definition 1.2. J(e,f) = I(e,f) + (1/2) sum over common endpoints v of sigma_v(e) sigma_v(f) T_v(e,f), with I the signed number of crossings and T_v the order sign from a cut at v.
• Cycle pairing (OpenAI) — Theorem 1.3. In every normal drawing, for all orientations and cuts, J(z,y) = 0 for any two cycles z, y. No hypothesis.
• Triangles — Lemma 2.1. The boundary of a triangle and a closed polygonal walk in general position have signed intersection zero. No hypothesis.
• Closed polygonal walks — Lemma 2.2. Two closed polygonal walks in general position have signed intersection zero. No hypothesis.
• Two chords in a disc — Lemma 3.1. The signed intersection of two directed chords with four distinct endpoints is half the sum of the products of endpoint coefficients and order signs from any cut. No hypothesis.
• Lagrange interpolation — Lemma 1.1. A polynomial of degree at most N-1 is determined by its values at N distinct nodes, by the Lagrange formula. No hypothesis.
• Barycentric weights — Corollary 1.2. The sum of A(u_p)/G'(u_p) over N distinct nodes is the coefficient of t^(N-1) in A, so it vanishes when deg A <= N-2. No hypothesis.
• Dividing by a linear factor — Lemma 2.1. A polynomial in two variables vanishing on a line u = c or v = c is divisible by u - c or v - c, with the degree bounds lowered by one. No hypothesis.
• The odd pattern (OpenAI) — Lemma 3.1. For distinct x_1, ..., x_(2s+1), evaluation at (x_p, x_q), (p,q) in the two-triangle pattern Q_s, is a bijection from the polynomials of degree at most s-1 in each variable onto R^(Q_s). No hypothesis.
• The even pattern (OpenAI) — Lemma 4.1. For s >= 2 and distinct u_1, ..., u_(2s), evaluation on the pattern L_s is a bijection from P_(s-1,s-2) and from P_(s-2,s-1) onto R^(L_s). No hypothesis.
• Rank at special points — Lemma 1.1. A polynomial matrix of rank at most r at infinitely many points has rank at most r everywhere. No hypothesis.
• Rank loss and multiple roots — Lemma 1.2. If a square polynomial matrix of size k has rank at most k-q at t_0, then (xi - t_0)^q divides its determinant. No hypothesis.
• Subspace intersection inequality (OpenAI) — Theorem 2.1. If U_i cap V_i = 0 for i = 1, ..., m in a real space of dimension N, then the sum of dim(U_i cap V_j) over all i, j is at most floor(m^2/4) N. No hypothesis.
• Sharpness — Remark 2.2. Two complementary subspaces and two groups of indices attain the bound floor(m^2/4) N.
• Ranks of differences (OpenAI) — Corollary 3.1. If X_i - Y_i is invertible for d x d matrices, i = 1, ..., m, then the sum of rank(X_i - Y_j) over i != j is at least 2 d_m d. No hypothesis.
• Blocks of a drawing of K_{m,n} — Lemma 1.1. In a normal drawing, the diagonal block J^{ii} is half the sign matrix of the order of the edges at a_i, and an off-diagonal entry of J^{ik} with p != q is a signed crossing count. No hypothesis.
• Block relation (OpenAI) — Lemma 2.1. J^{ik} - J^{i1} - J^{1k} + J^{11} is additive (of the form r_p + c_q). Uses the cycle pairing.
• The detector (OpenAI) — Lemma 3.1. For n = 2s+1 the interpolation map Phi kills additive and diagonal matrices, has rank at most one per nonzero off-diagonal entry, and maps the sign matrix of every linear order to an invertible matrix. No hypothesis.
• Odd n (OpenAI) — Proposition 4.1. For n odd, every normal drawing of K_{m,n} has at least d_m d_n pairs of independent edges with nonzero signed crossing count, hence at least d_m d_n crossings. No hypothesis.
• Even n — Proposition 5.1. For n even, cr(K_{m,n}) >= d_m d_n, by deleting one vertex of the second class at a time. No hypothesis.
• Zarankiewicz's formula (OpenAI) — Theorem 5.2. cr(K_{m,n}) = d_m d_n for all m, n >= 1. No hypothesis.
• Polynomial cycle tests (OpenAI) — Lemma 1.1. In a normal drawing of K_n, the sum of J([ip],[kq]) w_i w_p w_k w_q H(t_i,t_p,t_k,t_q) vanishes for every polynomial H of degree at most n-2 in each variable. No hypothesis.
• Order pairing (OpenAI) — Lemma 2.1. For 2s nodes and any linear order, the weighted order pairing is nondegenerate on P_(s-1,s-2) x P_(s-2,s-1). No hypothesis.
• Injectivity (OpenAI) — Lemma 3.1. For n = 2s+1, evaluating symmetric polynomials of degree at most s-2 in each variable at the ordered pairs of independent edges with nonzero signed crossing count is injective. No hypothesis.
• Odd n (OpenAI) — Proposition 4.1. For n = 2s+1 >= 5, every normal drawing of K_n has at least Z(n) pairs of independent edges with nonzero signed crossing count, hence at least Z(n) crossings. No hypothesis.
• The lower bound (OpenAI) — Theorem 5.1. cr(K_n) >= Z(n) for every n >= 3. No hypothesis.
• Two semicircles — Lemma 1.1. Semicircles over the axis in one half-plane cross exactly when their endpoints alternate, once and properly, and semicircles with one common endpoint meet only there. No hypothesis.
• The two-page drawing — Proposition 2.1. With suitable positions on the spine, the semicircle drawing of K_n with edges up or down by the endpoint sum modulo n is a drawing whose crossings are the same-colour alternating pairs. No hypothesis.
• The count (OpenAI) — Proposition 3.1. The endpoint-sum two-page drawing of K_n has exactly Z(n) crossing points. No hypothesis.
• The Harary-Hill formula (OpenAI) — Theorem 4.1. cr(K_n) = Z(n) for every n >= 3. No hypothesis.

Reading order

Read the lessons in order. The first two set up drawings, the third proves the cycle pairing, the fourth and fifth are algebra without drawings, and the last three prove the two formulas.