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
where
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
where
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 (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 , the independent odd crossing number of , which is the smallest number of pairs of independent edges that cross an odd number of times in any drawing of . By definition, .
Theorem 1. For all ,
The theorem also settles the value for 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 is non-trivial in the sense that we know that there are graphs for which [5]. For this question remains open: for all we know , though we do not expect this to be the case.
The same proof technique also yields the independent odd crossing number of . The OpenAI proof required some more conceptual machinery in this case.
Theorem 2. For all ,
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 . The drawing of 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 , in a drawing we define as the number of times and cross in . The crossing number of a drawing is defined as
With that the crossing number of is the smallest over all drawings of . If we count crossings modulo we obtain the odd crossing number of :
The odd crossing number of , , minimizes over all drawings of . If we only want to count the crossing pairs in a drawing, we set
and define the corresponding pair crossing number, as the smallest where ranges over all drawings of .
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 , in a drawing we label each crossing or depending on the direction in which crosses . The signed algebraic intersection number is the sum of the signed crossings of and ; flipping the direction of an edge only changes the sign of , so we can define the algebraic crossing number of as
The algebraic crossing number of , , is the minimum of over all drawings of . By definition, for all graphs .
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 , and yields eight variants, since (there are no crossings between adjacent edges in a -minimal drawing).
The tables below summarize these variants, they are based on figures from [3, 5].
Table 1.
Table 2.
The values of the crossing number variants in each table are non-decreasing as one moves rightwards and/or upwards. Since and 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 , and thereby (and ), 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 , 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 is a cyclic permutation of the edges incident to ; 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 be the counterclockwise permutation of the edges incident to as they attach to .
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 for the directed edge from to , and . Let (note that this convention is compatible with the notation: ). 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 can be extended to chains in . To this end we want to lift to pairs of curves . This is easy if and do not have any interfering endpoints, that is if and (for example, a pair of closed curves has no interfering endpoints): For two oriented curves with no interfering endpoints the signed algebraic intersection number 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 where are edge chains such that agrees with for chains with no interfering endpoints. The choice of function is not unique; we will use a particularly simple form. For every vertex we take the cyclic permutation of the edges around and turn it into a linear order by arbitrarily selecting one of the edges as the first edge in the rotation. The function can then be defined as the bilinear extension of the following equations:
The following lemma justifies this definition of .
Lemma 3.1. The bilinear extension of (1) agrees with the signed algebraic intersection number for chains with non-interfering endpoints.
Proof. For the proof we construct the intersection pairing by a systematic perturbation of the drawing 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 , meeting its incident edges in spokes. Choose a gap between two spokes at declaring them the first and last edges: . On the disk boundary add a red vertex and a blue vertex 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
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 when the tracks have the same orientation (Figure 2(b)). No other corridor crossings are needed.

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

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 , define
where follows along the red vertices and edges and follows along the blue vertices and edges; this gives an unambiguous definition of a bilinear intersection number . 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 directed away from , the two chords inside the disk cross if and only if , and then with sign $+1
({xref}Figure 2(a)`). All other crossings contribute .For the same directed edge , the red and blue chords cross with sign inside each endpoint disk. Their corridor crossing has sign , giving .
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 , as claimed.
Any two closed cycles in the plane have signed algebraic intersection number and since they do not have interfering endpoints, the value of must also be .
Corollary 3.1. For any two cycles in ,
An important property of the function is the following. For a vertex and distinct neighbors note that . We let be reduced modulo . When working in a field extension of we will extend bilinearly to that field extension. Note that
that is, 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 , for , where the ’s are independent variables and
are their Lagrange interpolation weights (these weights are rational functions of the ’s). Since the field has characteristic 2 we have .
A tournament is a matrix with entries in satisfying for (we don’t put any restriction on the diagonal entries). Let
Define the square matrix , with rows and columns indexed by , where and as follows.
Theorem 3. For any and for every tournament on vertices,
Let be the space of polynomials in variables with degree in and degree in . We adopt the convention that when or . We will apply Theorem 3 in the following form.
Corollary 4.1. Suppose satisfies
Then is the zero polynomial.
The crossing-number lower bound
Throughout this section and is an arbitrary drawing of . Let be independent variables, one for each vertex. We will work over a field . Define the Lagrange coefficients
Applying Lagrange interpolation to for at gives
Looking at the coefficient of on both sides we obtain
We say that a polynomial is symmetric in if swapping and does not change its value, that is,
Let be the family of 4-variable polynomials that have degree at most in each variable. Let contain polynomials that are symmetric in and in , that is . The symmetry condition is equivalent to having the coefficient of depend only on the two unordered exponent pairs and . This implies
The following definition is specific for fields of characteristic two. We say that a polynomial is alternating in if it is symmetric in and for the value of the polynomial is zero, that is,
Let contain polynomials that are alternating in and in . The alternation condition is equivalent to having the coefficient of depend only on the two unordered exponent pairs and , with the coefficient forced to zero if or . This implies
From (9) and Corollary 3.1 we obtain the following.
Lemma 5.1. For every polynomial in
For every polynomial in
Proof. Note that the sum in (14) is effectively over and since, by convention, we let . Let . The boundary of the chain is
using (9) in the final step. Expanding yields (14) for monomial . By linearity this extends to all .
For the alternating case, using we can write . Expanding yields (15) for . These polynomials span , so the identity follows by linearity to all .
Lemma 5.2. Suppose satisfies
Then is the zero polynomial.
Proof. Assume satisfies (17), , and choose such with minimum degree in . Note that for any four distinct vertices we have
because the assumption implies that at least one of the two terms in the product is 0.
Fix a vertex . Let be the elements of . Define
Note that are of degree and we have
Take any and let
Every variable in has degree at most and hence we can apply (14). By equation (18) all independent-edge terms are zero. The term zeroes out terms with , , and . Hence the only terms that survive in the sum (14) applied to are the ones with and with (the last equality is forced by (19)). Thus
where is the tournament for vertex (see (4)) and in the last sum are such that and hence
and similarly . Corollary 4.1 yields
as a polynomial in .
This holds for every vertex . Since has degree at most in , it follows that . Hence divides . By symmetry the product
also divides . But satisfies the same vanishing hypothesis, since is nonzero on four distinct vertex labels, and . This contradicts the choice of . Therefore .
Proof of Theorem 1. We can assume that . Let be the number of independent pairs of edges crossing oddly in and define
The purpose of the terms is to make the polynomial alternating; the purpose of the remaining terms is to eliminate dependent edges.
Let . Then . Let be the set of ordered pairs where , , are all distinct and . Note that , since each pair of independent edges crossing oddly occurs twice in . From (15), applied to we have
where
Note that for all factors on the right-hand-side of (24) are non-zero and hence . Also note that (23) is true for every pair of polynomials .
Let and suppose . By Lemma 5.2, evaluation on determines every polynomial in . Choose a subset of exactly points such that for every set of values on there is a unique polynomial in with those values (pick a basis of , for each consider the vector and use the Steinitz lemma to pick linearly independent vectors). Let . Since there is a nonzero vanishing at every point of . Hence for every we have
Since the values of are unrestricted (by our choice of ) we can conclude that for every . Thus vanishes on all of (which is equivalent to (17)) and contradicts Lemma 5.2. Hence .
This proves for odd . The lower bound for even 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 and use definitions (5) and (6). Let . The matrix represents the following bilinear form on
We also use an auxiliary bilinear form, obtained by inserting one more factor :
If then
Let and for let
The proof needs the following four lemmas. Their proofs are given in Sections 7 and 8.
Lemma 6.1. The form is symmetric and, for every ,
We also have
Lemma 6.2. The form is symmetric and for
Lemma 6.3. Every has a unique decomposition
Explicitly,
Lemma 6.4. For every non-zero we have .
Proof of Theorem 3. Suppose satisfies for every . We will argue that the only way this can happen is if (and hence is nonsingular). Taking and using Lemma 6.1 we obtain , where . By (28) we have
Write with using Lemma 6.3. Using Lemma 6.2 we have
Lemma 6.4 now implies and hence . Taking in (34) gives
and hence . Thus . We proved that , and therefore , is nonsingular.
Basic properties of - 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
Note that (35) implies that for a polynomial of degree we have . Similarly we can conclude that for every that has degree in or in
If is symmetric then the off-diagonal entries in (36) can be paired up (since ) to cancel, hence
Proof of Lemma 6.1. Let . Then . Swapping and using , we obtain
using (37) to extend the summation from to all pairs , and (36) in the last equality. This shows that is symmetric.
Let . Swapping and using , we obtain
again using (36) for the last equality.
To prove the final claim of the lemma assume . Derivatives of squares vanish in characteristic two and hence for every we have
Since the degree of is at most and it is zero for values we must have and hence divides (since viewed as a polynomial in has root ). ▫
Proof of Lemma 6.2. Let . Swapping and using , we obtain
where in the last equality we used (36) (expanding the square and dealing with and separately). Thus is symmetric.
Let . Then is also symmetric. Swapping and using , we obtain
where in the last equality we used (37)—applied to the symmetric polynomial —and (36).
Proof of Lemma 6.3. For the statement is trivially true (since the space for is ); assume . The numerator in (33) is when and hence it is divisible by . The division decreases the degree in each variable (if non-zero). Thus is a polynomial in . It is symmetric since its expression is invariant under swapping and .
The polynomial is also symmetric:
The degree of in is at most (since the bound is true for and ) and by symmetry the same bound holds for the degree of . Hence .
Suppose and and are symmetric. Swapping variables yields which combined with gives and hence and . This implies uniqueness for any (taking the difference of two purported solutions).
The differentiation lemma
For let
Lemma 8.1. For we have the following
Proof. The first equation in (39) is immediate from the definition. For the second we first collect basic facts on . We have
for and hence
for any . Using the product rule we also have
For the second equation in (39), using (41) and then (42), we obtain
Applying (35) yields (39).
Proof of Lemma 6.4. Suppose that satisfies , and choose such a with minimum degree in . Write
In terms of we have
For , apply to . Note that all 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 and hence
where in the second equality we used (since ).
We next apply , where . Again the square is annihilated and the only term we need to account for is . By (39),
We assumed and hence for all and . These monomials form a basis of , so
Since we have and, by Lemma 6.1, . Since is symmetric, so is ; moreover, , , and . Using (28), we obtain
Taking gives , contradicting the minimality of . Thus for every nonzero .
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 for odd and , where . Fix an arbitrary drawing of . Let the partitions of vertices be and .
Assign algebraically independent variables to the vertices in and to the vertices in . We work over and use the Lagrange weights
As in (9), Lagrange interpolation gives
Let denote the space of polynomials having degree at most in each of and at most in each of . Note that
Lemma 9.1. For every polynomial with degree at most in each of and at most in each of ,
Proof. For and , let
Then : as in Equation (16) we argue that the coefficient of is , and the coefficient of is , using (45). By Corollary 3.1, . Expanding this equality gives (47) for , where and . These monomials span , so the identity follows for every .
Lemma 9.2. Suppose satisfies
Then is the zero polynomial.
Proof. Suppose otherwise, and choose a nonzero satisfying (48) with minimum degree in . For all and we then have
Fix . Partition into two sets of size , and define
Both polynomials have degree , and
For any , take
The degree of in and is at most , and in and it is at most . We may therefore apply Lemma 9.1. Terms with vanish because of the factor . Terms with vanish by (49) (and the terms with have already been removed). In the remaining terms , so (50) forces . Hence,
where is the tournament for , that is, , see (4).
Corollary 4.1, with , , and , applies to the polynomial . Since (52) holds for every , it follows that
This is true for every . The polynomial has degree at most in and vanishes for . Hence it is identically zero, which implies that divides . The quotient is nonzero, belongs to , and still satisfies (48), since whenever . Its degree in is smaller, contradicting our choice of . Thus . □
Proof of Theorem 2. Let , and let be the set of ordered quadruples for which , , and . Each unordered pair of independent, odd-crossing edges appears twice, and hence .
Take arbitrary and let
The degree of in is at most , and its degree in is at most . The factors and eliminate all pairs of edges with a common endpoint. Applying Lemma 9.1, we obtain
where
Every appearing in (54) is nonzero, since and . The identity holds for every pair of polynomials .
Let . Suppose . By Lemma 9.2, evaluation on determines every polynomial in . Choose a subset of exactly points whose evaluation rows are linearly independent. Then for any prescribed values on there is a unique polynomial taking those values. Let . As , there exists a nonzero vanishing at every point of . For this choice of , equation (54) reduces, for every , to
Since the values of are unrestricted we can conclude for every point of . Thus vanishes on all of , contradicting Lemma 9.2. Hence .
This proves in case both and are odd. The remaining cases, where at least one of or is even, then follow from a standard counting argument which can be found in Guy [6]. Finally, the classical Zarankiewicz drawing has exactly crossings [18, 10]. Since , this gives the matching upper bound and completes the proof.
Open Questions
Harborth’s Conjecture The best known upper bound on the crossing number of the complete -partite graph 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 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 [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 vs 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]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]Martin Balko. Proof of the Harary–Hill conjecture: an exposition, 2026. arXiv:2610.34444.arxiv.org/abs/2610.34444
- [3]Peter Brass, William Moser, and János Pach. Research problems in discrete geometry. Springer, New York, 2005.DOI
- [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]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]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]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]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]Heiko Harborth. über die Kreuzungszahl vollständiger, n-geteilter Graphen. Math. Nachr., 48:179–188, 1971. doi:10.1002/mana.19710480113.DOI
- [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]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]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]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]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]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]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]W. T. Tutte. Toward a theory of crossing numbers. J. Combinatorial Theory, 8:45–53, 1970.DOI
- [18]K. Zarankiewicz. The solution of a certain problem on graphs of P. Turan. Bull. Acad. Polon. Sci. Cl. III., 1:167–168, 1953.