betaFeedback

WorksMathematics

Crossing Numbers of Complete Graphs: the independent odd crossing number

Abstract

We show that the Harary–Hill bound on the crossing number of complete graphs as well as the Zarankiewwicz bound on the crossing number of complete bipartite graphs, both recently established by OpenAI, also hold for the independent odd crossing number. This implies that the same bounds hold for several other crossing number variants such as the (independent) algebraic crossing number and the (independent) pair crossing number.

Introduction

The crossing number of a graph is the smallest number of crossings achievable in a drawing of the graph. Crossing number research for many decades has been inspired by two conjectures: Zarankiewicz [18] in the 1950s thought he had proven that

cr⁡(Km,n)=Z(m,n),\operatorname{cr}(K_{m,n}) = Z(m,n),

where

Z(m,n)=⌊m2⌋⌊m−12⌋⌊n2⌋⌊n−12⌋.Z(m,n) = \left\lfloor\frac{m}{2} \right\rfloor\left\lfloor\frac{m-1}{2} \right\rfloor\left\lfloor\frac{n}{2} \right\rfloor\left\lfloor\frac{n-1}{2} \right\rfloor.

There was a gap in his proof so the conjecture that his bound is correct is now known as the Zarankiewicz conjecture (for historical background, see Székely’s [16] paper). In the 1960s, Harary and Hill [8] conjectured that the crossing number of the complete graph is given by

cr⁡(Kn)=Z(n),\operatorname{cr}(K_n) = Z(n),

where

Z(n)=14⌊n2⌋⌊n−12⌋⌊n−22⌋⌊n−32⌋.Z(n) = \frac{1}{4} \left\lfloor\frac{n}{2} \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.

Both conjectures were recently proved by OpenAI [11, 10] and the Harary–Hill bound has already been rewritten for human readers by crossing number experts: Martin Balko [2] and Gelasio Salazar [14]. Balko showed that OpenAI’s result holds for the crossing number variant ocr⁡+\operatorname{ocr}_{+} (which we will define below), while Salazar, taking a combinatorial point of view, made progress towards Archdeacon’s conjecture (for background on the conjecture see [1]).

We give a third exposition of the OpenAI proof. Our goal is to strengthen the result by showing that the lower bound also applies to other ways of counting crossings in a graph. We focus on iocr⁡(G)\operatorname{iocr}(G), the independent odd crossing number of GG, which is the smallest number of pairs of independent edges that cross an odd number of times in any drawing of GG. By definition, iocr⁡(G)≤cr⁡(G)\operatorname{iocr}(G) \le\operatorname{cr}(G).

Theorem 1. For all n≥1n \ge1,

iocr⁡(Kn)=cr⁡(Kn)=Z(n).\operatorname{iocr}(K_n) = \operatorname{cr}(K_n) = Z(n).

The theorem also settles the value for KnK_n of many other crossing number variants, including the algebraic crossing number, the pair crossing number, and the independent crossing number [15 Open Question 2]. We will formally define these crossing numbers in the next section.

The result on iocr⁡(Kn)\operatorname{iocr}(K_n) is non-trivial in the sense that we know that there are graphs for which iocr⁡(G)<cr⁡(G)\operatorname{iocr}(G) < \operatorname{cr}(G) [5]. For ocr⁡+\operatorname{ocr}_{+} this question remains open: for all we know ocr⁡+(G)=cr⁡(G)\operatorname{ocr}_{+}(G) = \operatorname{cr}(G), though we do not expect this to be the case.

The same proof technique also yields the independent odd crossing number of Km,nK_{m,n}. The OpenAI proof required some more conceptual machinery in this case.

Theorem 2. For all m,n≥1m,n \ge1,

iocr⁡(Km,n)=cr⁡(Km,n)=Z(m,n).\operatorname{iocr}(K_{m,n}) = \operatorname{cr}(K_{m,n}) = Z(m,n).

Approach. The approach follows the framework used in OpenAI’s breakthrough. Each vertex in the drawing is assigned an independent algebraically independent variable in a field extension of F2\mathbb{F}_2. The drawing of KnK_n is then connected, using the concept of intersection pairings, to the evaluation of bounded-degree four-variable polynomials on quadruples of elements corresponding to pairs of independent edges crossing an odd number of times. Using properties of the drawing and the intersection pairing, it is shown that a non-zero polynomial in the space cannot ever evaluate to zero on all the points—establishing a lower bound on the number of pairs of independent edges crossing oddly in terms of the dimension of the space of the polynomials. The bound is within a factor of two of the desired bound and is then boosted by another refined dimension argument. An important ingredient, that is also present in the previous proofs, is a “localization argument” that gives regularity of a map arising from a local intersection pattern around a single vertex. For the independent odd crossing number the drawing allows dependent edges to intersect, resulting in more general intersection pairings and requiring a much stronger localization argument.

AI statement. This work has been produced with significant help of ChatGPT 5.6 Pro (understanding the previous results, exploring proof strategies, proving statements, and consulting alternative exposition paths). The authors take full responsibility for the presentation and validity of the results.

Crossing Numbers

We restrict ourselves to drawings of a graph in which each pair of edges crosses at most a finite number of times, no three edges cross in a point, and no edge passes through a vertex. For two edges ee, ff in a drawing DD we define cr⁡D(e,f)\operatorname{cr}_{D}(e,f) as the number of times ee and ff cross in DD. The crossing number of a drawing DD is defined as

cr⁡(D)=∑{e,f}cr⁡D(e,f).\operatorname{cr}(D) = \sum_{\{e,f\}} \operatorname{cr}_{D}(e,f).

With that the crossing number of GG is the smallest cr⁡(D)\operatorname{cr}(D) over all drawings DD of GG. If we count crossings modulo 22 we obtain the odd crossing number of DD:

\operatorname{ocr}(D)=\#\{\{e,f\}:\operatorname{cr}_D(e,f)=1\mathbin{\mod}2\}.

The odd crossing number of GG, ocr⁡(G)\operatorname{ocr}(G), minimizes ocr⁡(D)\operatorname{ocr}(D) over all drawings DD of GG. If we only want to count the crossing pairs in a drawing, we set

pcr⁡(D)=#{{e,f}:cr⁡D(e,f)≥1},\operatorname{pcr}(D)=\#\{\{e,f\}:\operatorname{cr}_D(e,f)\ge1\},

and define the corresponding pair crossing number, pcr⁡(G)\operatorname{pcr}(G) as the smallest pcr⁡(D)\operatorname{pcr}(D) where DD ranges over all drawings of GG.

We can also count crossings algebraically, an approach we will take in the proof (before reducing to the modulo 2 version). For two directed edges ee, ff in a drawing DD we label each crossing +1+1 or −1-1 depending on the direction in which ee crosses ff. The signed algebraic intersection number ID(e,f)I_D(e,f) is the sum of the signed crossings of ee and ff; flipping the direction of an edge only changes the sign of ID(e,f)I_D(e,f), so we can define the algebraic crossing number of DD as

acr⁡(D)=∑{e,f}∣ID(e,f)∣.\operatorname{acr}(D)=\sum_{\{e,f\}}\lvert I_D(e,f)\rvert.

The algebraic crossing number of GG, acr⁡(G)\operatorname{acr}(G), is the minimum of acr⁡(D)\operatorname{acr}(D) over all drawings of GG. By definition, ocr⁡(G)≤acr⁡(G)≤cr⁡(G)\operatorname{ocr}(G)\le\operatorname{acr}(G)\le\operatorname{cr}(G) for all graphs GG.

Pach and Tóth [12] initiated a systematic study of crossing number variants by introducing two rules that can be used with any crossing number: “Rule +” prohibits crossings between adjacent edges, while “Rule −” allows crossings between adjacent edges, but does not count them. Applying these rules to ocr⁡\operatorname{ocr}, acr⁡\operatorname{acr} and cr⁡\operatorname{cr} yields eight variants, since cr⁡+=cr⁡\operatorname{cr}_{+}=\operatorname{cr} (there are no crossings between adjacent edges in a cr⁡\operatorname{cr}-minimal drawing).

The tables below summarize these variants, they are based on figures from [3, 5].

ocr⁡+\operatorname{ocr}_{+}acr⁡+\operatorname{acr}_{+}cr⁡\operatorname{cr}
ocr⁡\operatorname{ocr}acr⁡\operatorname{acr}
ocr⁡−=iocr⁡\operatorname{ocr}_{-}=\operatorname{iocr}acr⁡−=iacr⁡\operatorname{acr}_{-}=\operatorname{iacr}cr⁡−\operatorname{cr}_{-}

Table 1.

ocr⁡+\operatorname{ocr}_{+}pcr⁡+\operatorname{pcr}_{+}cr⁡\operatorname{cr}
ocr⁡\operatorname{ocr}pcr⁡\operatorname{pcr}
ocr⁡−=iocr⁡\operatorname{ocr}_{-}=\operatorname{iocr}pcr⁡−\operatorname{pcr}_{-}cr⁡−\operatorname{cr}_{-}

Table 2.

The values of the crossing number variants in each table are non-decreasing as one moves rightwards and/or upwards. Since iocr⁡\operatorname{iocr} and cr⁡\operatorname{cr} are at extreme ends of both tables, Theorem 1 implies that the Harary–Hill bound holds for all of these crossing number variants.3

Balko [2] proves the Harary–Hill bound for ocr⁡+\operatorname{ocr}_{+}, and thereby acr⁡+\operatorname{acr}_{+} (and pcr⁡+\operatorname{pcr}_{+}), so his proof can handle the odd crossing count, but only if adjacent crossings are not allowed. Our main contribution is to show that not only can we allow adjacent crossings when counting crossings modulo 22, but that the crossing number does not change even if we do not count those crossings.

The main difference from the previous proofs and expositions is allowing dependent edges to cross. This changes how intersection pairing is defined (the second line in (1) accounts for such intersections) and this, in turn, requires a stronger claim for the localization of the polynomial method to a vertex (Theorem 3).

For the proof we will need the following terminology: The rotation at a vertex vv is a cyclic permutation of the edges incident to vv; a rotation system of a graph assigns a rotation to each vertex of the graph. A drawing of a graph determines a rotation system by letting the rotation at a vertex vv be the counterclockwise permutation of the edges incident to vv as they attach to vv.

Edge Chains and Intersection Pairings

Our proof, just like the other proofs [11, 2, 14], will be based on edge-chains, an idea introduced into crossing number research by Tutte in his famous “Toward a theory of crossing numbers” [17].

Write [uv]=−[vu][uv] = -[vu] for the directed edge from uu to vv, and ∂[uv]=[v]−[u]\partial[uv] = [v] - [u]. Let [uu]=0[uu] = 0 (note that this convention is compatible with the ∂\partial notation: ∂[uu]=[u]−[u]=0\partial[uu] = [u] - [u] = 0). An (edge) chain is an arbitrary linear combination of these symbols; a cycle has zero boundary (paths and cycles are special cases of an edge chain).

Our goal in this section is to explain how IDI_D can be extended to chains in GG. To this end we want to lift IDI_D to pairs of curves γ,η\gamma,\eta. This is easy if γ\gamma and η\eta do not have any interfering endpoints, that is if ∂γ∩η=∅\partial\gamma\cap\eta= \varnothing and ∂η∩γ=∅\partial\eta\cap\gamma= \varnothing (for example, a pair of closed curves has no interfering endpoints): For two oriented curves with no interfering endpoints the signed algebraic intersection number ID(γ,η)I_D(\gamma,\eta) is well-defined (the value is robust under sufficiently small perturbations of the curves, even if they share internal vertices or segments, or cross).

To carefully account for intersections of edges in the drawing we will need to extend the signed algebraic intersection number to curves that have interfering endpoints. We need an intersection pairing—a bilinear function RD′(z,z′)R'_D(z,z') where z,z′z,z' are edge chains such that RD′R'_D agrees with IDI_D for chains γ,η\gamma,\eta with no interfering endpoints. The choice of function RD′R'_D is not unique; we will use a particularly simple form. For every vertex vv we take the cyclic permutation of the edges around vv and turn it into a linear order ≺v\prec_v by arbitrarily selecting one of the edges as the first edge in the rotation. The function RD′R'_D can then be defined as the bilinear extension of the following equations:

RD′([uv],[wq])=ID([uv],[wq])if the edges are independent,RD′([vp],[vq])=ID([vp],[vq])+1{p≺vq}if p≠q,RD′([uv],[uv])=1.(1)\begin{aligned} R'_D([uv],[wq]) &= I_D([uv],[wq]) && \text{if the edges are independent,}\\ R'_D([vp],[vq]) &= I_D([vp],[vq]) + 1\{p \prec_v q\} && \text{if }p \ne q,\\ R'_D([uv],[uv]) &= 1. \tag*{(1)} \end{aligned}

The following lemma justifies this definition of RD′R'_D.

Lemma 3.1. The bilinear extension of (1) agrees with the signed algebraic intersection number IDI_D for chains γ,η\gamma,\eta with non-interfering endpoints.

Proof. For the proof we construct the intersection pairing by a systematic perturbation of the drawing DD such that for any two curves whose signed algebraic intersection number we are computing these curves do not have interfering endpoints; the bilinearity then follows from the bilinearity of the signed algebraic intersection number.

Take a small disk around each vertex vv, meeting its incident edges in spokes. Choose a gap between two spokes at vv declaring them the first and last edges: e1≺v⋯≺vede_1 \prec_v \cdots\prec_v e_d. On the disk boundary add a red vertex rvr_v and a blue vertex bvb_v within the gap, and a red and a blue vertex, which we call ports, beside each spoke, the red port slightly clockwise of the blue one. Thus the boundary points occur counterclockwise in the order

rv, bv, rv,e1, bv,e1,…,rv,ed, bv,ed.(2)r_v,\ b_v,\ r_{v,e_1},\ b_{v,e_1},\ldots,r_{v,e_d},\ b_{v,e_d}. \tag*{(2)}

Join each colored vertex to its ports by straight chords inside the disk.

Outside the disks, run colored copies of each edge in a narrow corridor along the original edge. At a crossing of distinct original edges, the red copy of one and the blue copy of the other cross once, with the original sign.

Along a single edge, the red port is clockwise of the blue port at both ends. Since the two outward directions are opposite, the red and blue tracks lie on opposite relative sides of the edge at its two ends. We therefore join them with exactly one crossing in the corridor, of sign −1-1 when the tracks have the same orientation (Figure 2(b)). No other corridor crossings are needed.

Ordered red–blue resolution

Figure 2. The ordered red–blue resolution. Only the red copy of ee and blue copy of ff are drawn in (a); the other ports illustrate their order. The two copies of a single edge switch sides in (b).

The red–blue resolution at a vertex

Figure 1. The red–blue resolution at a vertex. The original spokes are shown dashed. Each color connects its vertex in the chosen gap to the corresponding ports on the disk boundary.

For edge chains z,z′z,z', define

RD′(z,z′):=I(zred,(z′)blue),R'_D(z,z') := I\left(z^{\mathrm{red}},(z')^{\mathrm{blue}}\right),

where zredz^{\mathrm{red}} follows zz along the red vertices and edges and (z′)blue(z')^{\mathrm{blue}} follows z′z' along the blue vertices and edges; this gives an unambiguous definition of a bilinear intersection number RD′R'_D. We check that it satisfies (1):

  • For edges with no common endpoint, the red–blue crossings are exactly the original crossings, with the same signs.

  • For distinct edges [vp],[vq][vp],[vq] directed away from vv, the two chords inside the disk cross if and only if p≺vqp \prec_v q, and then with sign $+1 ({xref}Figure 2(a)`). All other crossings contribute ID([vp],[vq])I_D([vp],[vq]).

  • For the same directed edge [uv][uv], the red and blue chords cross with sign +1+1 inside each endpoint disk. Their corridor crossing has sign −1-1, giving RD′([uv],[uv])=1+1−1=1R'_D([uv],[uv]) = 1 + 1 - 1 = 1.

Reversing an edge reverses the sign, so these cases determine the pairing on all oriented edges and prove (1).

Finally, the red and blue copies of any two chains are arbitrarily small perturbations of the original chains. If their endpoints are non-interfering, such perturbations preserve their signed algebraic intersection number. Hence RD′(γ,η)=ID(γ,η)R'_D(\gamma,\eta)=I_D(\gamma,\eta), as claimed.

Any two closed cycles in the plane have signed algebraic intersection number 00 and since they do not have interfering endpoints, the value of RD′R'_D must also be 00.

Corollary 3.1. For any two cycles z,z′z,z' in GG,

RD′(z,z′)=0.(3)R'_D(z,z')=0. \tag*{(3)}

An important property of the function RD′R'_D is the following. For a vertex vv and distinct neighbors p,qp,q note that RD′([vp],[vq])+RD′([vq],[vp])=1R'_D([vp],[vq])+R'_D([vq],[vp])=1. We let RDR_D be RD′R'_D reduced modulo 22. When working in a field extension of F2\mathbb{F}_2 we will extend RDR_D bilinearly to that field extension. Note that

RD([vp],[vq])+RD([vq],[vp])=1,(4)R_D([vp],[vq])+R_D([vq],[vp])=1, \tag*{(4)}

that is, L(p,q):=RD([vp],[vq])L(p,q):=R_D([vp],[vq]) is a “tournament” (we will define this presently).

Local detector

In this section we state the local detector theorem, a non-trivial algebraic fact which is at the core of the strengthened crossing-number argument. We postpone the proof to Sections 6–8.

We work over the rational-function field K=F2(u1,…,uN)\mathbb{K}=\mathbb{F}_2(u_1,\ldots,u_N), for N≥3N \ge3, where the upu_p’s are independent variables and

λp:=1∏q≠p(up+uq).(5)\lambda_p := \frac{1}{\prod_{q\ne p}(u_p+u_q)} . \tag*{(5)}

are their Lagrange interpolation weights (these weights are rational functions of the upu_p’s). Since the field has characteristic 2 we have X+Y=X−YX+Y=X-Y.

A tournament is a matrix LL with entries in F2\mathbb{F}_2 satisfying Lpq+Lqp=1L_{pq}+L_{qp}=1 for p≠qp\ne q (we don’t put any restriction on the diagonal entries). Let

s1=⌊N−32⌋,s2=⌊N−32⌋.s_1=\left\lfloor\frac{N-3}{2}\right\rfloor,\qquad s_2=\left\lfloor\frac{N-3}{2}\right\rfloor.

Define the square (s1+1)(s2+1)×(s1+1)(s2+1)(s_1+1)(s_2+1)\times(s_1+1)(s_2+1) matrix MN(L)M_N(L), with rows and columns indexed by (a,b)(a,b), where 0≤a≤s10\le a\le s_1 and 0≤b≤s20\le b\le s_2 as follows.

MN(L)(a,b),(c,d)=∑p≠qLpqλpλq(up+uq)upa+duqb+c.(6)M_N(L)_{(a,b),(c,d)}=\sum_{p\ne q}L_{pq}\lambda_p\lambda_q(u_p+u_q)u_p^{a+d}u_q^{b+c}. \tag*{(6)}

Theorem 3. For any N≥3N\ge3 and for every tournament LL on NN vertices,

det⁡MN(L)≠0in F2(u1,…,uN).\det M_N(L)\ne0\quad\text{in }\mathbb{F}_2(u_1,\ldots,u_N).

Let Pa,b\mathcal{P}_{a,b} be the space of polynomials in variables X,YX,Y with degree ≤a\le a in XX and degree ≤b\le b in YY. We adopt the convention that Pa,b={0}\mathcal{P}_{a,b}=\{0\} when a<0a<0 or b<0b<0. We will apply Theorem 3 in the following form.

Corollary 4.1. Suppose P∈Ps1,s2P\in\mathcal{P}_{s_1,s_2} satisfies

∑p≠qLpqλpλq(up+uq)P(up,uq)Q(up,uq)=0for every Q∈Ps2,s1.(7)\sum_{p\ne q}L_{pq}\lambda_p\lambda_q(u_p+u_q)P(u_p,u_q)Q(u_p,u_q)=0\quad\text{for every }Q\in\mathcal{P}_{s_2,s_1}. \tag*{(7)}

Then PP is the zero polynomial.

The crossing-number lower bound

Throughout this section n=2s+1≥5n=2s+1\ge5 and DD is an arbitrary drawing of KnK_n. Let t1,…,tnt_1,\ldots,t_n be independent variables, one for each vertex. We will work over a field K⊇F2(t1,…,tn)K\supseteq\mathbb{F}_2(t_1,\ldots,t_n). Define the Lagrange coefficients

ωi=1∏j≠i(ti+tj).\omega_i=\frac{1}{\prod_{j\ne i}(t_i+t_j)}.

Applying Lagrange interpolation to xax^a for 0≤a≤n−10\le a\le n-1 at t1,…,tnt_1,\ldots,t_n gives

xa=∑i=1ntia∏j≠itj+xti+tj=∑i=1nωitia∏j≠i(tj+x).(8)x^a=\sum_{i=1}^{n}t_i^a\prod_{j\ne i}\frac{t_j+x}{t_i+t_j}=\sum_{i=1}^{n}\omega_i t_i^a\prod_{j\ne i}(t_j+x). \tag*{(8)}

Looking at the coefficient of xn−1x^{n-1} on both sides we obtain

∑iωitia=0 for a∈{0,…,n−2}and∑iωitin−1=1.(9)\sum_i\omega_i t_i^a=0\text{ for }a\in\{0,\ldots,n-2\}\quad\text{and}\quad\sum_i\omega_i t_i^{n-1}=1. \tag*{(9)}

We say that a polynomial P(x1,…,xn)P(x_1,\ldots,x_n) is symmetric in (xi,xj)(x_i,x_j) if swapping xix_i and xjx_j does not change its value, that is,

P(x1,…,xi,…,xj,…,xn)=P(x1,…,xj,…,xi,…,xn).(10)P(x_1,\ldots,x_i,\ldots,x_j,\ldots,x_n)=P(x_1,\ldots,x_j,\ldots,x_i,\ldots,x_n). \tag*{(10)}

Let PkP_k be the family of 4-variable polynomials that have degree at most kk in each variable. Let Sk⊆PkS_k\subseteq P_k contain polynomials that are symmetric in (x,u)(x,u) and in (y,v)(y,v), that is P(u,x,y,v)=P(x,u,y,v)P(u,x,y,v)=P(x,u,y,v). The symmetry condition is equivalent to having the coefficient of xaubycvdx^a u^b y^c v^d depend only on the two unordered exponent pairs {a,b}\{a,b\} and {c,d}\{c,d\}. This implies

dim⁡Sk=(k+22)2=Z(2k+5).(11)\dim S_k=\binom{k+2}{2}^{2}=Z(2k+5). \tag*{(11)}

The following definition is specific for fields of characteristic two. We say that a polynomial P(x1,…,xn)P(x_1,\ldots,x_n) is alternating in (xi,xj)(x_i,x_j) if it is symmetric in (xi,xj)(x_i,x_j) and for xi=xjx_i=x_j the value of the polynomial is zero, that is,

P(x1,…,xi,…,xi,…,xn)=0.(12)P(x_1,\ldots,x_i,\ldots,x_i,\ldots,x_n)=0. \tag*{(12)}

Let Ak⊆SkA_k\subseteq S_k contain polynomials that are alternating in (x,u)(x,u) and in (y,v)(y,v). The alternation condition is equivalent to having the coefficient of xaubycvdx^a u^b y^c v^d depend only on the two unordered exponent pairs {a,b}\{a,b\} and {c,d}\{c,d\}, with the coefficient forced to zero if a=ba=b or c=dc=d. This implies

dim⁡Ak=(k+12)2=Z(2k+3).(13)\dim A_k=\binom{k+1}{2}^{2}=Z(2k+3). \tag*{(13)}

From (9) and Corollary 3.1 we obtain the following.

Lemma 5.1. For every polynomial H(x,u,y,v)H(x,u,y,v) in Pn−2P_{n-2}

∑i,j,k,ℓ=1nωiωjωkωℓRD([ij],[kℓ])H(ti,tj,tk,tℓ)=0.(14)\sum_{i,j,k,\ell=1}^{n}\omega_i\omega_j\omega_k\omega_\ell R_D([ij],[k\ell])H(t_i,t_j,t_k,t_\ell)=0. \tag*{(14)}

For every polynomial H(x,u,y,v)H(x,u,y,v) in An−2A_{n-2}

∑i<j∑k<ℓωiωjωkωℓRD([ij],[kℓ])H(ti,tj,tk,tℓ)=0.(15)\sum_{i<j}\sum_{k<\ell}\omega_i\omega_j\omega_k\omega_\ell R_D([ij],[k\ell])H(t_i,t_j,t_k,t_\ell)=0. \tag*{(15)}

Proof. Note that the sum in (14) is effectively over i≠ji \ne j and k≠ℓk \ne\ell since, by convention, we let [ii]=0[ii]=0. Let 0≤a,b≤n−20 \le a,b \le n-2. The boundary of the chain zab=∑i,jωiωjtiatjb[ij]z_{ab}=\sum_{i,j}\omega_i\omega_jt_i^at_j^b[ij] is

∂zab=∑i,jωiωjtiatjb([i]+[j])=∑i[i]ωitia∑jωjtjb+∑j[j]ωjtjb∑iωitia=0,(16)\partial z_{ab}=\sum_{i,j}\omega_i\omega_jt_i^at_j^b([i]+[j])=\sum_i[i]\omega_it_i^a\sum_j\omega_jt_j^b+\sum_j[j]\omega_jt_j^b\sum_i\omega_it_i^a=0, \tag*{(16)}

using (9) in the final step. Expanding RD(zab,zcd)=0R_D(z_{ab},z_{cd})=0 yields (14) for monomial xaubycvdx^au^by^cv^d. By linearity this extends to all HH.

For the alternating case, using [ij]=[ji][ij]=[ji] we can write zab=∑i<jωiωj(tiatjb+tibtja)[ij]z_{ab}=\sum_{i<j}\omega_i\omega_j(t_i^at_j^b+t_i^bt_j^a)[ij]. Expanding RD(zab,zcd)=0R_D(z_{ab},z_{cd})=0 yields (15) for (xaub+xbua)(ycvd+ydvc)(x^au^b+x^b u^a)(y^cv^d+y^dv^c). These polynomials span An−2A_{n-2}, so the identity follows by linearity to all HH.

Lemma 5.2. Suppose P∈Ss−2P\in S_{s-2} satisfies

P(ti,tj,tk,tℓ)=0for all distinct i,j,k,ℓ such that RD([ij],[kℓ])=1.(17)P(t_i,t_j,t_k,t_\ell)=0\quad\text{for all distinct }i,j,k,\ell\text{ such that }R_D([ij],[k\ell])=1. \tag*{(17)}

Then PP is the zero polynomial.

Proof. Assume P(x,u,y,v)∈Ss−2P(x,u,y,v)\in S_{s-2} satisfies (17), P≠0P\ne0, and choose such PP with minimum degree in xx. Note that for any four distinct vertices i,j,k,ℓi,j,k,\ell we have

RD([ij],[kℓ])P(ti,tj,tk,tℓ)=0,(18)R_D([ij],[k\ell])P(t_i,t_j,t_k,t_\ell)=0, \tag*{(18)}

because the assumption implies that at least one of the two terms in the product is 0.

Fix a vertex ii. Let u1,…,u2su_1,\ldots,u_{2s} be the elements of {t1,…,tn}∖{ti}\{t_1,\ldots,t_n\}\setminus\{t_i\}. Define

Ui(x)=∏j∈{1,…,s}x+ujti+ujandVi(x)=∏j∈{s+1,…,2s}x+ujti+uj.U_i(x)=\prod_{j\in\{1,\ldots,s\}}\frac{x+u_j}{t_i+u_j} \quad\text{and}\quad V_i(x)=\prod_{j\in\{s+1,\ldots,2s\}}\frac{x+u_j}{t_i+u_j}.

Note that Ui,ViU_i,V_i are of degree ss and we have

Ui(tj)Vi(tj)={1,j=i,0,j≠i.(19)U_i(t_j)V_i(t_j)= \begin{cases} 1, & j=i,\\ 0, & j\ne i. \end{cases} \tag*{(19)}

Take any Q∈Ps−1,s−1Q\in P_{s-1,s-1} and let

H=P(x,u,y,v)(u+v)(u+y)(v+x)Ui(x)Vi(y)Q(u,v).(20)H=P(x,u,y,v)(u+v)(u+y)(v+x)U_i(x)V_i(y)Q(u,v). \tag*{(20)}

Every variable in HH has degree at most 2s−1=n−22s-1=n-2 and hence we can apply (14). By equation (18) all independent-edge terms are zero. The term (u+v)(u+y)(v+x)(u+v)(u+y)(v+x) zeroes out terms with u=vu=v, u=yu=y, and v=xv=x. Hence the only terms that survive in the sum (14) applied to HH are the ones with x=yx=y and with x=y=tix=y=t_i (the last equality is forced by (19)). Thus

0=∑i′,j,k,ℓ∈[n]ωi′ωjωkωℓRD([i′j],[kℓ])H(ti′,tj,tk,tℓ)=ωi2∑j≠ℓ∈[n]j,ℓ≠iωjωℓRD([ij],[iℓ])(ti+tj)(ti+tℓ)(tj+tℓ)P(ti,tj,ti,tℓ)Q(tj,tℓ)=ωi2∑p≠q∈[2s]L(p,q)(up+uq)λpλqP(ti,up,ti,uq)Q(up,uq).\begin{aligned} 0&=\sum_{\substack{i',j,k,\ell\in[n]}}\omega_{i'}\omega_j\omega_k\omega_\ell R_D([i'j],[k\ell])H(t_{i'},t_j,t_k,t_\ell)\\ &=\omega_i^2\sum_{\substack{j\ne\ell\in[n]\\j,\ell\ne i}}\omega_j\omega_\ell R_D([ij],[i\ell])(t_i+t_j)(t_i+t_\ell)(t_j+t_\ell)P(t_i,t_j,t_i,t_\ell)Q(t_j,t_\ell)\\ &=\omega_i^2\sum_{\substack{p\ne q\in[2s]}}L(p,q)(u_p+u_q)\lambda_p\lambda_qP(t_i,u_p,t_i,u_q)Q(u_p,u_q). \end{aligned}

where LL is the tournament for vertex ii (see (4)) and in the last sum p,qp, q are such that up=tj,uq=tℓu_p=t_j,u_q=t_\ell and hence

λp=1∏r≠p(up+ur)=1∏k≠i,j(tk+tj)=(ti+tj)1∏k≠j(tk+tj)=(ti+tj)ωj,\lambda_p=\frac{1}{\prod_{r\ne p}(u_p+u_r)}=\frac{1}{\prod_{k\ne i,j}(t_k+t_j)}=(t_i+t_j)\frac{1}{\prod_{k\ne j}(t_k+t_j)}=(t_i+t_j)\omega_j,

and similarly λq=(ti+tℓ)ωℓ\lambda_q=(t_i+t_\ell)\omega_\ell. Corollary 4.1 yields

P(ti,u,ti,v)=0(21)P(t_i,u,t_i,v)=0 \tag*{(21)}

as a polynomial in u,vu,v.

This holds for every vertex ii. Since P(x,u,x,v)P(x,u,x,v) has degree at most 2s−4<n2s-4<n in xx, it follows that P(x,u,x,v)≡0P(x,u,x,v)\equiv0. Hence x+yx+y divides P(x,u,y,v)P(x,u,y,v). By symmetry the product

C=(x+y)(x+v)(u+y)(u+v)(22)C=(x+y)(x+v)(u+y)(u+v) \tag*{(22)}

also divides PP. But P/C∈Ss−2P/C\in S_{s-2} satisfies the same vanishing hypothesis, since CC is nonzero on four distinct vertex labels, and deg⁡x(P/C)=deg⁡xP−2\deg_x(P/C)=\deg_x P-2. This contradicts the choice of PP. Therefore P=0P=0.

Proof of Theorem 1. We can assume that n≥5n\ge5. Let w=iocr⁡(D)w=\operatorname{iocr}(D) be the number of independent pairs of edges crossing oddly in DD and define

Θ=(x+u)(y+v)(x+y)(x+v)(u+y)(u+v).\Theta=(x+u)(y+v)(x+y)(x+v)(u+y)(u+v).

The purpose of the (x+u)(y+v)(x+u)(y+v) terms is to make the polynomial alternating; the purpose of the remaining terms is to eliminate dependent edges.

Let P(x,u,y,v),Q(x,u,y,v)∈Ss−2P(x,u,y,v),Q(x,u,y,v)\in S_{s-2}. Then PQΘ∈An−2PQ\Theta\in A_{n-2}. Let TDT_D be the set of ordered pairs ((i,j),(k,ℓ))((i,j),(k,\ell)) where i<ji<j, k<ℓk<\ell, i,j,k,ℓi,j,k,\ell are all distinct and RD([ij],[kℓ])=1R_D([ij],[k\ell])=1. Note that ∣TD∣=2w|T_D|=2w, since each pair of independent edges crossing oddly occurs twice in TDT_D. From (15), applied to H=PQΘ∈An−2H=PQ\Theta\in A_{n-2} we have

∑((i,j),(k,ℓ))∈TDαi,j,k,ℓP(ti,tj,tk,tℓ)Q(ti,tj,tk,tℓ)=0,(23)\sum_{((i,j),(k,\ell))\in T_D}\alpha_{i,j,k,\ell}P(t_i,t_j,t_k,t_\ell)Q(t_i,t_j,t_k,t_\ell)=0, \tag*{(23)}

where

αi,j,k,ℓ=ωiωjωkωℓ(ti+tj)(ti+tk)(ti+tℓ)(tj+tk)(tj+tℓ)(tk+tℓ).(24)\alpha_{i,j,k,\ell}=\omega_i\omega_j\omega_k\omega_\ell(t_i+t_j)(t_i+t_k)(t_i+t_\ell)(t_j+t_k)(t_j+t_\ell)(t_k+t_\ell). \tag*{(24)}

Note that for ((i,j),(k,ℓ))∈TD((i,j),(k,\ell))\in T_D all factors on the right-hand-side of (24) are non-zero and hence αi,j,k,ℓ≠0\alpha_{i,j,k,\ell}\ne0. Also note that (23) is true for every pair of polynomials P(x,u,y,v),Q(x,u,y,v)∈Ss−2P(x,u,y,v),Q(x,u,y,v)\in S_{s-2}.

Let d=dim⁡Ss−2d=\dim S_{s-2} and suppose w<dw<d. By Lemma 5.2, evaluation on TDT_D determines every polynomial in Ss−2S_{s-2}. Choose a subset T1⊆TDT_1\subseteq T_D of exactly dd points such that for every set of values on T1T_1 there is a unique polynomial in Ss−2S_{s-2} with those values (pick a basis B1,…,BdB_1,\ldots,B_d of Ss−2S_{s-2}, for each α∈TD\alpha\in T_D consider the vector (B1(α),…,Bd(α))(B_1(\alpha),\ldots,B_d(\alpha)) and use the Steinitz lemma to pick dd linearly independent vectors). Let T2=TD∖T1T_2=T_D\setminus T_1. Since ∣T2∣=2w−d<d|T_2|=2w-d<d there is a nonzero Q(x,u,y,v)∈Ss−2Q(x,u,y,v)\in S_{s-2} vanishing at every point of T2T_2. Hence for every P(x,u,y,v)∈Ss−2P(x,u,y,v)\in S_{s-2} we have

∑((i,j),(k,ℓ))∈T1αi,j,k,ℓP(ti,tj,tk,tℓ)Q(ti,tj,tk,tℓ)=0.(25)\sum_{((i,j),(k,\ell))\in T_1}\alpha_{i,j,k,\ell}P(t_i,t_j,t_k,t_\ell)Q(t_i,t_j,t_k,t_\ell)=0. \tag*{(25)}

Since the values of PP are unrestricted (by our choice of T1T_1) we can conclude that Q(ti,tj,tk,tℓ)=0Q(t_i,t_j,t_k,t_\ell)=0 for every ((i,j),(k,ℓ))∈T1((i,j),(k,\ell))\in T_1. Thus QQ vanishes on all of TDT_D (which is equivalent to (17)) and contradicts Lemma 5.2. Hence w≥d=dim⁡Ss−2w\ge d=\dim S_{s-2}.

This proves iocr⁡(Kn)≥Z(n)\operatorname{iocr}(K_n)\ge Z(n) for odd n=2s+1n=2s+1. The lower bound for even nn then follows a standard counting argument going back to Guy [7]. The upper bound is shown in the paper by Harary and Hill [8] that started it all. ∎

The local detector: the algebraic argument

We now prove Theorem 3. We fix a tournament LL and use definitions (5) and (6). Let V=Ps1,s2\mathcal{V}=\mathcal{P}_{s_1,s_2}. The matrix MNM_N represents the following bilinear form on V\mathcal{V}

B(f,g)=∑p≠qLpqλpλq(up+uq)f(up,uq)g(uq,up).(26)B(f,g)=\sum_{p\ne q}L_{pq}\lambda_p\lambda_q(u_p+u_q)f(u_p,u_q)g(u_q,u_p). \tag*{(26)}

We also use an auxiliary bilinear form, obtained by inserting one more factor up+uqu_p+u_q:

A(f,g)=∑p≠qLpqλpλq(up+uq)2f(up,uq)g(uq,up).(27)A(f,g)=\sum_{p\ne q}L_{pq}\lambda_p\lambda_q(u_p+u_q)^2f(u_p,u_q)g(u_q,u_p). \tag*{(27)}

If f,g,(X+Y)f∈Vf,g,(X+Y)f\in\mathcal{V} then

A(f,g)=B((X+Y)f,g).(28)A(f,g)=B((X+Y)f,g). \tag*{(28)}

Let U={g∈Ps1−1,s1−1:g(X,Y)=g(Y,X)}⊆V\mathcal{U}=\{g\in\mathcal{P}_{s_1-1,s_1-1}:g(X,Y)=g(Y,X)\}\subseteq\mathcal{V} and for g∈Ug\in\mathcal{U} let

Φ(g)=A(g,Xg).\Phi(g)=A(g,Xg).

The proof needs the following four lemmas. Their proofs are given in Sections 7 and 8.

Lemma 6.1. The form BB is symmetric and, for every f∈Vf\in\mathcal{V},

B(f,f)=∑pup(λpf(up,up))2.(29)B(f,f)=\sum_p u_p\left(\lambda_p f(u_p,u_p)\right)^2. \tag*{(29)}

We also have

B(f,f)=0⟹(X+Y)∣f.(30)B(f,f)=0\quad\Longrightarrow\quad(X+Y)\mid f. \tag*{(30)}

Lemma 6.2. The form AA is symmetric and for g0,g1∈Ug_0,g_1\in\mathcal{U}

A(g0,g1)=0.(31)A(g_0,g_1)=0. \tag*{(31)}

Lemma 6.3. Every h∈Ps1−1,s2−1h\in\mathcal{P}_{s_1-1,s_2-1} has a unique decomposition

h=h0+Xh1,h0,h1∈U.(32)h=h_0+Xh_1,\qquad h_0,h_1\in\mathcal{U}. \tag*{(32)}

Explicitly,

h1=h(X,Y)+h(Y,X)X+Y,h0=h+Xh1.(33)h_1=\frac{h(X,Y)+h(Y,X)}{X+Y},\qquad h_0=h+Xh_1. \tag*{(33)}

Lemma 6.4. For every non-zero g∈Ug\in\mathcal{U} we have Φ(g)≠0\Phi(g)\ne0.

Proof of Theorem 3. Suppose f∈Vf\in\mathcal{V} satisfies B(f,v)=0B(f,v)=0 for every v∈Vv\in\mathcal{V}. We will argue that the only way this can happen is if f=0f=0 (and hence BB is nonsingular). Taking v=fv=f and using Lemma 6.1 we obtain f=(X+Y)hf=(X+Y)h, where h∈Ps1−1,s2−1h\in\mathcal{P}_{s_1-1,s_2-1}. By (28) we have

A(h,v)=0 for every v∈V.(34)A(h,v)=0\text{ for every }v\in\mathcal{V}. \tag*{(34)}

Write h=h0+Xh1h=h_0+Xh_1 with h0,h1∈Uh_0,h_1\in\mathcal{U} using Lemma 6.3. Using Lemma 6.2 we have

0=A(h,h1)=A(h0,h1)+A(Xh1,h1)=A(h1,Xh1)=Φ(h1).0=A(h,h_1)=A(h_0,h_1)+A(Xh_1,h_1)=A(h_1,Xh_1)=\Phi(h_1).

Lemma 6.4 now implies h1=0h_1=0 and hence h=h0∈Uh=h_0\in\mathcal{U}. Taking v=Xh0v=Xh_0 in (34) gives

0=A(h0,Xh0)=Φ(h0),0=A(h_0,Xh_0)=\Phi(h_0),

and hence h0=0h_0=0. Thus h=f=0h=f=0. We proved that BB, and therefore MN(L)M_N(L), is nonsingular.

Basic properties of A,B\mathcal{A},\mathcal{B} - proofs of Lemmas 6.1, 6.2, 6.3

We use the following fact about Lagrange interpolation coefficients (see argument after (8) for a proof). For 0≤a≤N−20 \leq a \leq N-2

∑pλpupa=0and∑pλpupN−1=1.(35)\sum_p \lambda_p u_p^a=0 \quad\text{and} \quad\sum_p \lambda_p u_p^{N-1}=1. \tag*{(35)}

Note that (35) implies that for a polynomial ff of degree ≤N−2\leq N-2 we have ∑pλpf(up)=0\sum_p \lambda_p f(u_p)=0. Similarly we can conclude that for every f(X,Y)f(X,Y) that has degree ≤N−2\leq N-2 in XX or in YY

∑p,qλpλqf(up,uq)=0.(36)\sum_{p,q}\lambda_p\lambda_q f(u_p,u_q)=0. \tag*{(36)}

If f∈PN−2,N−2f \in\mathcal{P}_{N-2,N-2} is symmetric then the off-diagonal entries in (36) can be paired up (since λpλqf(up,uq)=λqλpf(uq,up)\lambda_p\lambda_qf(u_p,u_q)=\lambda_q\lambda_pf(u_q,u_p)) to cancel, hence

∑pλp2f(up,up)=0.(37)\sum_p \lambda_p^2f(u_p,u_p)=0. \tag*{(37)}

Proof of Lemma 6.1. Let f,g∈Vf,g \in\mathcal{V}. Then f(X,Y)g(Y,X)∈PN−3,N−3f(X,Y)g(Y,X) \in\mathcal{P}_{N-3,N-3}. Swapping p,qp,q and using Lpq+Lqp=1L_{pq}+L_{qp}=1, we obtain

B(f,g)+B(g,f)=∑p≠qλpλq(up+uq)f(up,uq)g(uq,up)=∑p,qλpλq(up+uq)f(up,uq)g(uq,up)=0,\begin{aligned} \mathcal{B}(f,g)+\mathcal{B}(g,f) &=\sum_{p\ne q}\lambda_p\lambda_q(u_p+u_q)f(u_p,u_q)g(u_q,u_p)\\ &=\sum_{p,q}\lambda_p\lambda_q(u_p+u_q)f(u_p,u_q)g(u_q,u_p)=0, \end{aligned}

using (37) to extend the summation from p≠qp\ne q to all pairs p,qp,q, and (36) in the last equality. This shows that B\mathcal{B} is symmetric.

Let f∈Vf\in\mathcal{V}. Swapping p,qp,q and using Lpq+Lqp=1L_{pq}+L_{qp}=1, we obtain

B(f,f)=∑p<qλpλq(up+uq)f(up,uq)f(uq,up)=∑p≠qλpλqupf(up,uq)f(uq,up)=∑pλp2upf(up,up)2+∑p,qλpλqupf(up,uq)f(uq,up)=∑pλp2upf(up,up)2,\begin{aligned} \mathcal{B}(f,f) &=\sum_{p<q}\lambda_p\lambda_q(u_p+u_q)f(u_p,u_q)f(u_q,u_p)\\ &=\sum_{p\ne q}\lambda_p\lambda_q u_p f(u_p,u_q)f(u_q,u_p)\\ &=\sum_p\lambda_p^2u_pf(u_p,u_p)^2+\sum_{p,q}\lambda_p\lambda_qu_pf(u_p,u_q)f(u_q,u_p)\\ &=\sum_p\lambda_p^2u_pf(u_p,u_p)^2, \end{aligned}

again using (36) for the last equality.

To prove the final claim of the lemma assume B(f,f)=0\mathcal{B}(f,f)=0. Derivatives of squares vanish in characteristic two and hence for every j∈[N]j\in[N] we have

0=∂∂ujB(f,f)=∑p∂∂ujλp2upf(up,up)2=∑p(∂∂uj(λpf(up,up))2up+(λp2f(up,up)2)∂∂ujup)=λj2f(uj,uj)2.\begin{aligned} 0=\frac{\partial}{\partial u_j}\mathcal{B}(f,f) &=\sum_p\frac{\partial}{\partial u_j}\lambda_p^2u_pf(u_p,u_p)^2\\ &=\sum_p\left(\frac{\partial}{\partial u_j}(\lambda_pf(u_p,u_p))^2u_p+(\lambda_p^2f(u_p,u_p)^2)\frac{\partial}{\partial u_j}u_p\right) =\lambda_j^2f(u_j,u_j)^2. \end{aligned}

Since the degree of f(X,X)f(X,X) is at most N−3<NN-3<N and it is zero for NN values we must have f(X,X)=0f(X,X)=0 and hence X+YX+Y divides f(X,Y)f(X,Y) (since ff viewed as a polynomial in XX has root YY). ▫

Proof of Lemma 6.2. Let f,g∈Vf,g \in\mathcal{V}. Swapping p,qp,q and using Lpq+Lqp=1L_{pq}+L_{qp}=1, we obtain

A(f,g)+A(g,f)=∑p≠qλpλq(up+uq)2f(up,uq)g(uq,up)=∑p,qλpλq(up+uq)2f(up,uq)g(uq,up)=0,\begin{aligned} \mathcal{A}(f,g)+\mathcal{A}(g,f) &=\sum_{p\ne q}\lambda_p\lambda_q(u_p+u_q)^2f(u_p,u_q)g(u_q,u_p)\\ &=\sum_{p,q}\lambda_p\lambda_q(u_p+u_q)^2f(u_p,u_q)g(u_q,u_p)=0, \end{aligned}

where in the last equality we used (36) (expanding the square and dealing with up2u_p^2 and uq2u_q^2 separately). Thus A\mathcal{A} is symmetric.

Let g0,g1∈Ug_0,g_1\in\mathcal{U}. Then g:=g0g1g:=g_0g_1 is also symmetric. Swapping p,qp,q and using Lpq+Lqp=1L_{pq}+L_{qp}=1, we obtain

A(g0,g1)=∑p<qλpλq(up+uq)2g(up,uq)=∑p≠qλpλqup2g(up,uq)=∑pλp2up2g(up,up)+∑p,qλpλqup2g(up,uq)=0,\begin{aligned} \mathcal{A}(g_0,g_1) &=\sum_{p<q}\lambda_p\lambda_q(u_p+u_q)^2g(u_p,u_q)\\ &=\sum_{p\ne q}\lambda_p\lambda_q u_p^2g(u_p,u_q)\\ &=\sum_p\lambda_p^2u_p^2g(u_p,u_p)+\sum_{p,q}\lambda_p\lambda_q u_p^2g(u_p,u_q)=0, \end{aligned}

where in the last equality we used (37)—applied to the symmetric polynomial XYg(X,Y)XYg(X,Y)—and (36).

Proof of Lemma 6.3. For s2=0s_2=0 the statement is trivially true (since the space for hh is {0}\{0\}); assume s2≥1s_2\ge1. The numerator in (33) is 00 when X=YX=Y and hence it is divisible by X+YX+Y. The division decreases the degree in each variable (if non-zero). Thus h1h_1 is a polynomial in U\mathcal{U}. It is symmetric since its expression is invariant under swapping XX and YY.

The polynomial h0=h+Xh1h_0=h+Xh_1 is also symmetric:

h0(X,Y)=h(X,Y)+Xh1(X,Y)=h(X,Y)+Yh1(X,Y)+(X+Y)h1(X,Y)=h(Y,X)+Yh1(Y,X)=h0(Y,X).\begin{aligned} h_0(X,Y)&=h(X,Y)+Xh_1(X,Y)=h(X,Y)+Yh_1(X,Y)+(X+Y)h_1(X,Y)\\ &=h(Y,X)+Yh_1(Y,X)=h_0(Y,X). \end{aligned}

The degree of YY in h0h_0 is at most max⁡{s2−1,s1−2}≤s1−1\max\{s_2-1,s_1-2\}\le s_1-1 (since the bound is true for hh and h1h_1) and by symmetry the same bound holds for the degree of XX. Hence h0∈Uh_0\in\mathcal{U}.

Suppose h0+Xh1=0h_0+Xh_1=0 and h0h_0 and h1h_1 are symmetric. Swapping variables yields h0+Yh1=0h_0+Yh_1=0 which combined with h0+Xh1=0h_0+Xh_1=0 gives (X+Y)h1=0(X+Y)h_1=0 and hence h1=0h_1=0 and h0=0h_0=0. This implies uniqueness for any h∈Ps1−1,s2−1h\in\mathcal{P}_{s_1-1,s_2-1} (taking the difference of two purported solutions).

The differentiation lemma

For 0≤a≤N−10\le a\le N-1 let

Da=∑r=1Nλrura∂∂ur.(38)\mathcal{D}_a=\sum_{r=1}^{N}\lambda_r u_r^a\frac{\partial}{\partial u_r}. \tag*{(38)}

Lemma 8.1. For 0≤a≤N−10\le a\le N-1 we have the following

Daup=λpupa,Daλp={0,a even,λp2upa−1,a odd.(39)\mathcal{D}_a u_p=\lambda_pu_p^a,\qquad \mathcal{D}_a\lambda_p= \begin{cases} 0, & a\ \text{even},\\ \lambda_p^2u_p^{a-1}, & a\ \text{odd}. \end{cases} \tag*{(39)}

Proof. The first equation in (39) is immediate from the definition. For the second we first collect basic facts on (∂/∂ur)(\partial/\partial u_r). We have

∂λp∂ur=λpup+ur(40)\frac{\partial\lambda_p}{\partial u_r}=\frac{\lambda_p}{u_p+u_r} \tag*{(40)}

for p≠rp\ne r and hence

λr∂λp∂ur=λp∂λr∂up(41)\lambda_r\frac{\partial\lambda_p}{\partial u_r}=\lambda_p\frac{\partial\lambda_r}{\partial u_p} \tag*{(41)}

for any p,r∈[N]p,r\in[N]. Using the product rule we also have

∂(λrupa)∂up=upa∂λr∂up+1r=p aλpupa−1(42)\frac{\partial(\lambda_r u_p^a)}{\partial u_p}=u_p^a\frac{\partial\lambda_r}{\partial u_p}+1_{r=p}\,a\lambda_pu_p^{a-1} \tag*{(42)}

For the second equation in (39), using (41) and then (42), we obtain

Daλp=∑r=1Nλrura∂λp∂ur=λp∑r=1Nura∂λr∂up=λp∂∂up(∑r=1Nλrura)+aλp2upa−1.\mathcal{D}_a\lambda_p=\sum_{r=1}^{N}\lambda_ru_r^a\frac{\partial\lambda_p}{\partial u_r} =\lambda_p\sum_{r=1}^{N}u_r^a\frac{\partial\lambda_r}{\partial u_p} =\lambda_p\frac{\partial}{\partial u_p}\left(\sum_{r=1}^{N}\lambda_ru_r^a\right)+a\lambda_p^2u_p^{a-1}.

Applying (35) yields (39).

Proof of Lemma 6.4. Suppose that 0≠g∈U0\ne g\in\mathcal{U} satisfies Φ(g)=0\Phi(g)=0, and choose such a gg with minimum degree in XX. Write

Gpq=(up+uq)g(up,uq).G_{pq}=(u_p+u_q)g(u_p,u_q).

In terms of GG we have

Φ(g)=∑p≠qLpqλpλquqGpq2.(43)\Phi(g)=\sum_{p\ne q}L_{pq}\lambda_p\lambda_qu_qG_{pq}^{2}. \tag*{(43)}

For 0≤a≤s10\le a\le s_1, apply D2a\mathcal{D}_{2a} to Φ(g)\Phi(g). Note that all λp\lambda_p are annihilated using (39) and all squares are annihilated (since we work in characteristic 2). The only term that we need to account for is uqu_q and hence

D2aΦ(g)=∑p≠qLpqλpλq2uq2aGpq2=∑pλp(∑q≠pLpqλquqaGpq)2,\mathcal{D}_{2a}\Phi(g)=\sum_{p\ne q}L_{pq}\lambda_p\lambda_q^{2}u_q^{2a}G_{pq}^{2} =\sum_p\lambda_p\left(\sum_{q\ne p}L_{pq}\lambda_qu_q^aG_{pq}\right)^2,

where in the second equality we used Lpq2=LpqL_{pq}^2=L_{pq} (since Lpq∈{0,1}L_{pq}\in\{0,1\}).

We next apply D2b+1\mathcal{D}_{2b+1}, where 0≤b≤s20\le b\le s_2. Again the square is annihilated and the only term we need to account for is λp\lambda_p. By (39),

D2b+1D2aΦ(g)=∑pλp2up2b(∑q≠pLpqλquqaGpq)2=(∑p≠qLpqλpλqupbuqaGpq)2=B(g,XaYb)2.(44)\begin{aligned} \mathcal{D}_{2b+1}\mathcal{D}_{2a}\Phi(g)=\sum_p\lambda_p^2u_p^{2b}\left(\sum_{q\ne p}L_{pq}\lambda_qu_q^aG_{pq}\right)^2 \\ &=\left(\sum_{p\ne q}L_{pq}\lambda_p\lambda_qu_p^bu_q^aG_{pq}\right)^2 =\mathcal{B}(g,X^aY^b)^2. \tag*{(44)} \end{aligned}

We assumed Φ(g)=0\Phi(g)=0 and hence B(g,XaYb)=0\mathcal{B}(g,X^aY^b)=0 for all 0≤a≤s10\le a\le s_1 and 0≤b≤s20\le b\le s_2. These monomials form a basis of V\mathcal{V}, so

B(g,v)=0for every v∈V.\mathcal{B}(g,v)=0\qquad\text{for every }v\in\mathcal{V}.

Since g∈U⊆Vg\in\mathcal{U}\subseteq\mathcal{V} we have B(g,g)=0\mathcal{B}(g,g)=0 and, by Lemma 6.1, g=(X+Y)hg=(X+Y)h. Since gg is symmetric, so is hh; moreover, h∈Uh\in\mathcal{U}, h≠0h\ne0, and deg⁡Xh<deg⁡Xg\deg_Xh<\deg_Xg. Using (28), we obtain

A(h,v)=B(g,v)=0for every v∈V.\mathcal{A}(h,v)=\mathcal{B}(g,v)=0\qquad\text{for every }v\in\mathcal{V}.

Taking v=Xh∈Vv=Xh\in\mathcal{V} gives Φ(h)=A(h,Xh)=0\Phi(h)=\mathcal{A}(h,Xh)=0, contradicting the minimality of deg⁡Xg\deg_Xg. Thus Φ(g)≠0\Phi(g)\ne0 for every nonzero g∈Ug\in\mathcal{U}.

The complete bipartite case

We apply the same techniques to complete bipartite graphs. We follow the structure of the proof in § 5, using similar ingredients: a cycle identity, a localization lemma, and then a second application of the identity to obtain the tight bound.

We first prove the lower bound on iocr⁡(Km,n)\operatorname{iocr}(K_{m,n}) for odd m=2r+1m=2r+1 and n=2s+1n=2s+1, where r,s≥1r,s\ge1. Fix an arbitrary drawing DD of Km,nK_{m,n}. Let the partitions of vertices be {1,…,m}\{1,\ldots,m\} and {1′,…,n′}\{1',\ldots,n'\}.

Assign algebraically independent variables t1,…,tmt_1,\ldots,t_m to the vertices in {1,…,m}\{1,\ldots,m\} and u1,…,unu_1,\ldots,u_n to the vertices in {1′,…,n′}\{1',\ldots,n'\}. We work over K=F2(t1,…,tm,u1,…,un)\mathbb{K}=\mathbb{F}_2(t_1,\ldots,t_m,u_1,\ldots,u_n) and use the Lagrange weights

αi=1∏h≠i(ti+th),βp=1∏q≠p(up+uq).\alpha_i=\frac{1}{\prod_{h\ne i}(t_i+t_h)},\qquad\beta_p=\frac{1}{\prod_{q\ne p}(u_p+u_q)}.

As in (9), Lagrange interpolation gives

∑iαitia=0(0≤a≤m−2),∑pβpupb=0(0≤b≤n−2).(45)\sum_i\alpha_i t_i^a=0\quad(0\le a\le m-2),\qquad\sum_p\beta_pu_p^b=0\quad(0\le b\le n-2). \tag*{(45)}

Let Sr,sS_{r,s} denote the space of polynomials P(x,u,y,v)P(x,u,y,v) having degree at most rr in each of x,yx,y and at most ss in each of u,vu,v. Note that

dim⁡Sr−1,s−1=r2s2=Z(m,n).(46)\dim S_{r-1,s-1}=r^2s^2=Z(m,n). \tag*{(46)}

Lemma 9.1. For every polynomial H(x,u,y,v)H(x,u,y,v) with degree at most m−2m-2 in each of x,yx,y and at most n−2n-2 in each of u,vu,v,

∑i,k=1m∑p,q=1nαiαkβpβqRD([ip′],[kq′])H(ti,up,tk,uq)=0.(47)\sum_{i,k=1}^{m}\sum_{p,q=1}^{n}\alpha_i\alpha_k\beta_p\beta_qR_D([ip'],[kq'])H(t_i,u_p,t_k,u_q)=0. \tag*{(47)}

Proof. For 0≤a≤m−20\le a\le m-2 and 0≤b≤n−20\le b\le n-2, let

zab=∑i=1m∑p=1nαiβptiaupb[ip′].z_{ab}=\sum_{i=1}^{m}\sum_{p=1}^{n}\alpha_i\beta_pt_i^au_p^b[ ip' ].

Then ∂zab=0\partial z_{ab}=0: as in Equation (16) we argue that the coefficient of [i][i] is αitia∑pβpupb=0\alpha_it_i^a\sum_p\beta_pu_p^b=0, and the coefficient of [p′][p'] is βpupb∑iαitia=0\beta_pu_p^b\sum_i\alpha_it_i^a=0, using (45). By Corollary 3.1, RD(zab,zcd)=0R_D(z_{ab},z_{cd})=0. Expanding this equality gives (47) for H(x,u,y,v)=xaubycvdH(x,u,y,v)=x^au^by^cv^d, where 0≤a,c≤m−20\le a,c\le m-2 and 0≤b,d≤n−20\le b,d\le n-2. These monomials span Sm−1,n−1S_{m-1,n-1}, so the identity follows for every HH.

Lemma 9.2. Suppose P∈Sr−1,s−1P\in S_{r-1,s-1} satisfies

P(ti,up,tk,uq)=0whenever i≠k, p≠q, RD([ip′],[kq′])=1.(48)P(t_i,u_p,t_k,u_q)=0\quad\text{whenever }i\ne k,\ p\ne q,\ R_D([ip'],[kq'])=1. \tag*{(48)}

Then PP is the zero polynomial.

Proof. Suppose otherwise, and choose a nonzero P∈Sr−1,s−1P\in S_{r-1,s-1} satisfying (48) with minimum degree in xx. For all i≠ki\ne k and p≠qp\ne q we then have

RD([ip′],[kq′])P(ti,up,tk,uq)=0.(49)R_D([ip'],[kq'])P(t_i,u_p,t_k,u_q)=0. \tag*{(49)}

Fix j∈[m]j\in[m]. Partition [m]∖{j}[m]\setminus\{j\} into two sets J1,J2J_1,J_2 of size rr, and define

Uj(x)=∏h∈J1x+thtj+th,Vj(y)=∏h∈J2y+thtj+th.U_j(x)=\prod_{h\in J_1}\frac{x+t_h}{t_j+t_h},\qquad V_j(y)=\prod_{h\in J_2}\frac{y+t_h}{t_j+t_h}.

Both polynomials have degree rr, and

Uj(ti)Vj(ti)={1,i=j,0,i≠j.(50)U_j(t_i)V_j(t_i)= \begin{cases} 1, & i=j,\\ 0, & i\ne j. \end{cases} \tag*{(50)}

For any Q(u,v)∈Ps−1,s−1Q(u,v)\in\mathcal{P}_{s-1,s-1}, take

H(x,u,y,v)=P(x,u,y,v)(u+v)Uj(x)Vj(y)Q(u,v).(51)H(x,u,y,v)=P(x,u,y,v)(u+v)U_j(x)V_j(y)Q(u,v). \tag*{(51)}

The degree of HH in xx and yy is at most (r−1)+r=2r−1=m−2(r-1)+r=2r-1=m-2, and in uu and vv it is at most (s−1)+1+(s−1)=2s−1=n−2(s-1)+1+(s-1)=2s-1=n-2. We may therefore apply Lemma 9.1. Terms with p=qp=q vanish because of the factor u+vu+v. Terms with i≠ki\ne k vanish by (49) (and the terms with p=qp=q have already been removed). In the remaining terms i=ki=k, so (50) forces i=k=ji=k=j. Hence,

0=αj2∑p≠qLpqβpβq(up+uq)P(tj,up,tj,uq)Q(up,uq),(52)0=\alpha_j^2\sum_{p\ne q}L_{pq}\beta_p\beta_q(u_p+u_q)P(t_j,u_p,t_j,u_q)Q(u_p,u_q), \tag*{(52)}

where LL is the tournament for jj, that is, Lpq=RD([jp′],[jq′])L_{pq}=R_D([jp'],[jq']), see (4).

Corollary 4.1, with N=n=2s+1N=n=2s+1, s1=s2=s−1s_1=s_2=s-1, and λp=βp\lambda_p=\beta_p, applies to the polynomial F(u,v)=P(tj,u,tj,v)∈Ps−1,s−1F(u,v)=P(t_j,u,t_j,v)\in\mathcal{P}_{s-1,s-1}. Since (52) holds for every Q∈Ps−1,s−1Q\in\mathcal{P}_{s-1,s-1}, it follows that

P(tj,u,tj,v)=0as a polynomial in u,v.(53)P(t_j,u,t_j,v)=0\qquad\text{as a polynomial in }u,v. \tag*{(53)}

This is true for every j∈[m]j\in[m]. The polynomial P(x,u,x,v)P(x,u,x,v) has degree at most 2r−2<m2r-2<m in xx and vanishes for x=t1,…,tmx=t_1,\ldots,t_m. Hence it is identically zero, which implies that x+yx+y divides P(x,u,y,v)P(x,u,y,v). The quotient P/(x+y)P/(x+y) is nonzero, belongs to Sr−1,s−1\mathcal{S}_{r-1,s-1}, and still satisfies (48), since ti+tk≠0t_i+t_k\ne0 whenever i≠ki\ne k. Its degree in xx is smaller, contradicting our choice of PP. Thus P=0P=0. □

Proof of Theorem 2. Let w=iocr⁡(D)w=\operatorname{iocr}(D), and let TDT_D be the set of ordered quadruples (i,p,k,q)(i,p,k,q) for which i≠ki\ne k, p≠qp\ne q, and RD([ip′],[kq′])=1R_D([ip'],[kq'])=1. Each unordered pair of independent, odd-crossing edges appears twice, and hence ∣TD∣=2w|T_D|=2w.

Take arbitrary P,Q∈Sr−1,s−1P,Q\in\mathcal{S}_{r-1,s-1} and let

H(x,u,y,v)=P(x,u,y,v)Q(x,u,y,v)(x+y)(u+v).H(x,u,y,v)=P(x,u,y,v)Q(x,u,y,v)(x+y)(u+v).

The degree of HH in x,yx,y is at most 2(r−1)+1=m−22(r-1)+1=m-2, and its degree in u,vu,v is at most 2(s−1)+1=n−22(s-1)+1=n-2. The factors x+yx+y and u+vu+v eliminate all pairs of edges with a common endpoint. Applying Lemma 9.1, we obtain

∑(i,p,k,q)∈TDγipkqP(ti,up,tk,uq)Q(ti,up,tk,uq)=0,(54)\sum_{(i,p,k,q)\in T_D}\gamma_{ipkq}P(t_i,u_p,t_k,u_q)Q(t_i,u_p,t_k,u_q)=0, \tag*{(54)}

where

γipkq=αiαkβpβq(ti+tk)(up+uq).\gamma_{ipkq}=\alpha_i\alpha_k\beta_p\beta_q(t_i+t_k)(u_p+u_q).

Every γipkq\gamma_{ipkq} appearing in (54) is nonzero, since i≠ki\ne k and p≠qp\ne q. The identity holds for every pair of polynomials P,Q∈Sr−1,s−1P,Q\in\mathcal{S}_{r-1,s-1}.

Let d=dim⁡Sr−1,s−1=r2s2d=\dim\mathcal{S}_{r-1,s-1}=r^2s^2. Suppose w<dw<d. By Lemma 9.2, evaluation on TDT_D determines every polynomial in Sr−1,s−1\mathcal{S}_{r-1,s-1}. Choose a subset T1⊆TDT_1\subseteq T_D of exactly dd points whose evaluation rows are linearly independent. Then for any prescribed values on T1T_1 there is a unique polynomial P∈Sr−1,s−1P\in\mathcal{S}_{r-1,s-1} taking those values. Let T2=TD∖T1T_2 = T_D \setminus T_1. As ∣T2∣=2w−d<d|T_2| = 2w-d < d, there exists a nonzero Q∈Sr−1,s−1Q \in S_{r-1,s-1} vanishing at every point of T2T_2. For this choice of QQ, equation (54) reduces, for every P∈Sr−1,s−1P \in S_{r-1,s-1}, to

∑(i,p,k,q)∈T1γipkqP(ti,up,tk,uq)Q(ti,up,tk,uq)=0.(55)\sum_{(i,p,k,q)\in T_1} \gamma_{ipkq} P(t_i,u_p,t_k,u_q)Q(t_i,u_p,t_k,u_q)=0. \tag*{(55)}

Since the values of PP are unrestricted we can conclude Q(ti,up,tk,uq)=0Q(t_i,u_p,t_k,u_q)=0 for every point of T1T_1. Thus QQ vanishes on all of TDT_D, contradicting Lemma 9.2. Hence w≥d=r2s2=Z(2r+1,2s+1)w \ge d=r^2s^2=Z(2r+1,2s+1).

This proves iocr⁡(Km,n)≥Z(m,n)\operatorname{iocr}(K_{m,n}) \ge Z(m,n) in case both mm and nn are odd. The remaining cases, where at least one of mm or nn is even, then follow from a standard counting argument which can be found in Guy [6]. Finally, the classical Zarankiewicz drawing has exactly Z(m,n)Z(m,n) crossings [18, 10]. Since iocr⁡≤cr⁡\operatorname{iocr} \le\operatorname{cr}, this gives the matching upper bound and completes the proof.

Open Questions

Harborth’s Conjecture The best known upper bound Z(n1,…,nk)Z(n_1,\ldots,n_k) on the crossing number of the complete kk-partite graph Kn1,…,nkK_{n_1,\ldots,n_k} was found by Harborth [9], also see [4 Theorem 2.1]. Harborth conjectured that this bound is optimal. Can the edge chain approach be adapted to prove Harborth’s conjecture? The case k=3k=3 would be a good starting point.

How close are iocr and cr? All the crossing number variants we have mentioned in this paper are polynomially related; this follows from cr⁡(G)≤(2iocr⁡(G)2)\operatorname{cr}(G) \le\binom{2\operatorname{iocr}(G)}{2} [13]. While we do know that some of these crossing numbers differ, e.g. iocr and ocr as mentioned earlier, this question remains open for many other variants, e.g. for cr⁡−\operatorname{cr}^{-} vs cr⁡\operatorname{cr} or, famously, pcr vs cr. Maybe Tutte’s crossing chains as developed in the OpenAI approach can lead to new insights on these questions.

References

  1. [1]Alan Arroyo, Dan McQuillan, R. Bruce Richter, and Gelasio Salazar. Drawings of K_n with the same rotation scheme are the same up to triangle-flips (Gioan’s theorem). Australas. J. Combin., 67:131–144, 2017.DOI
  2. [2]Martin Balko. Proof of the Harary–Hill conjecture: an exposition, 2026. arXiv:2610.34444.arxiv.org/abs/2610.34444
  3. [3]Peter Brass, William Moser, and János Pach. Research problems in discrete geometry. Springer, New York, 2005.DOI
  4. [4]Kieran Clancy, Michael Haythorpe, and Alex Newcombe. A survey of graphs with known or bounded crossing numbers. Australas. J. Combin., 78:209–296, 2020.arxiv.org/abs/1901.05155
  5. [5]Radoslav Fulek, Michael J. Pelsmajer, Marcus Schaefer, and Daniel Štefankovič. Adjacent crossings do matter. Journal of Graph Algorithms and Applications, 16(3):759–782, 2012. doi:10.7155/jgaa.00266.DOI
  6. [6]Richard K. Guy. The decline and fall of Zarankiewicz’s theorem. In Proof Techniques in Graph Theory (Proc. Second Ann Arbor Graph Theory Conf., Ann Arbor, Mich., 1968), pages 63–69. Academic Press, New York-London, 1969.
  7. [7]Richard K. Guy. Crossing numbers of graphs. In Graph theory and applications (Proc. Conf., Western Michigan Univ., Kalamazoo, Mich., 1972; dedicated to the memory of J. W. T. Youngs), volume Vol. 303 of Lecture Notes in Math., pages 111–124. Springer, Berlin-New York, 1972.DOI
  8. [8]Frank Harary and Anthony Hill. On the number of crossings in a complete graph. Proc. Edinburgh Math. Soc. (2), 13:333–338, 1963.DOI
  9. [9]Heiko Harborth. über die Kreuzungszahl vollständiger, n-geteilter Graphen. Math. Nachr., 48:179–188, 1971. doi:10.1002/mana.19710480113.DOI
  10. [10]OpenAI. The crossing number of complete bipartite graphs, 2026. OpenAI Math Release preprint, September 23, 2026. Identifier: OAI:The-crossing-number-of-complete-bipartite-graphs-September-23-2026. URL: https://github.com/openai/math/blob/main/preprints/The-crossing-number-of-complete-bipartite-graphs-September-23-2026.
  11. [11]OpenAI. The crossing number of complete graphs, 2026. OpenAI Math Release preprint, September 23, 2026. Identifier: OAI:The-crossing-number-of-complete-graphs-September-23-2026. URL: https://github.com/openai/math/tree/main/preprints/The-crossing-number-of-complete-graphs-September-23-2026.
  12. [12]János Pach and Géza Tóth. Which crossing number is it anyway? J. Combin. Theory Ser. B, 80(2):225–246, 2000.DOI
  13. [13]Michael J. Pelsmajer, Marcus Schaefer, and Daniel Štefankovič. Removing independently even crossings. SIAM J. Discrete Math., 24(2):379–393, 2010. doi:10.1137/090765729.DOI
  14. [14]Gelasio Salazar. The proof of the Harary–Hill conjecture: a detailed exposition and an extension to rotation systems, 2026. arXiv:2611.03515.arxiv.org/abs/2611.03515
  15. [15]Marcus Schaefer. The graph crossing number and its variants: a survey. Electron. J. Combin., DS21: updated May 17, 2024, 2013. doi:10.37236/2713.DOI
  16. [16]László A. Székely. Turán’s brick factory problem: the status of the conjectures of Zarankiewicz and Hill. In Ralucca Gera, Stephen Hedetniemi, and Craig Larson, editors, Graph theory—favorite conjectures and open problems. 1, Probl. Books in Math., pages 211–230. Springer, 2016. doi:10.1007/978-3-319-31940-7_13.DOI
  17. [17]W. T. Tutte. Toward a theory of crossing numbers. J. Combinatorial Theory, 8:45–53, 1970.DOI
  18. [18]K. Zarankiewicz. The solution of a certain problem on graphs of P. Turan. Bull. Acad. Polon. Sci. Cl. III., 1:167–168, 1953.

Paper details

vlnc:W_x2yfmuxs
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents