1 · The essentials
Imagine drawing dots on a sheet of paper and joining specified pairs with lines that may bend. The question is how few crossings you can achieve by choosing where the dots and lines go. One manuscript treats the case where every dot must connect to every other dot. Its companion treats two groups of dots, with every dot in one group connected to every dot in the other, and no connections within either group. The supplied source reports exact formulas for the smallest possible number of crossings in both cases, for every positive choice of group size. It states that the classical drawings already achieve these minima, even when competing drawings may use continuous curves rather than straight lines. Both manuscripts are marked as Lean-formalized.
A picture to help (an imperfect image, not to be taken literally)
As an imperfect image, imagine laying strings between marked spots on a tabletop and trying to arrange them with as few crossings as possible. The two problems prescribe different sets of required connections; the formulas say how many crossings cannot be avoided. Real strings have thickness and can pass over one another, so this is only an image of the mathematical drawing problem.
Why it matters
A drawing with few crossings gives a candidate answer, but optimality requires ruling out every drawing with fewer crossings. The source reports that the classical drawings are optimal for both complete graphs and complete bipartite graphs. It identifies these results with the Harary–Hill conjecture and the Zarankiewicz formulation of Turán's brickyard problem.
2 · Going further
The ordinary crossing number asks for the minimum number of edge crossings among plane drawings of a graph. The source allows continuous edge arcs, so the optimization is not restricted to straight-line drawings. For the complete graph , every pair of distinct vertices is connected; for the complete bipartite graph , the vertices form two groups of sizes and , with all connections between groups and none within a group.
The main manuscript states that, for every positive integer , . Here means the greatest integer no larger than . The source identifies this as the Harary–Hill formula and marks the manuscript as Lean-formalized.
The companion manuscript states that, for all positive integers , . It identifies this as the Zarankiewicz crossing-number conjecture, resolving Turán's brickyard problem, and is also marked as Lean-formalized. Thus the two manuscripts address the same minimization question for two different families of graphs.
The repository summary describes the shared conclusion as the optimality of the classical drawings among all plane drawings with continuous edge arcs. The supplied abstracts state the formulas but do not describe an argument or its main mechanism. Consequently, they do not support a more detailed explanation of how the necessary lower bounds are established.
Useful notions
- Graphs as vertices joined by edges
- Drawing graphs in the plane
- Minimization over possible drawings
- Complete and complete bipartite graphs
- The floor function
What was known before / what is new
Before
The source names the Harary–Hill and Zarankiewicz crossing-number conjectures as the problems being resolved. It also refers to classical drawings whose optimality is at issue. It supplies no history, earlier partial results, or account of how those drawings are constructed.
New
The main manuscript gives the exact crossing number of every complete graph with a positive number of vertices. The companion gives the exact crossing number of every complete bipartite graph whose two groups have positive sizes. According to the repository summary, these results establish that the classical drawings are optimal even against drawings using continuous edge arcs.
Limits and assumptions
The stated formulas concern ordinary crossing numbers in the plane, with positive integer parameters: for complete graphs and for complete bipartite graphs. They do not state a result for arbitrary graphs or other drawing settings. Both manuscripts are explicitly marked as Lean-formalized, including the main result, but the supplied text gives no formalization files or finer account of verification scope. The abstracts contain no proof strategy and identify no remaining open question.
Mini glossary
- Crossing number —
- The smallest number of edge crossings achievable in a plane drawing of a graph.
- Complete graph —
- A graph in which every pair of distinct vertices is joined by an edge.
- Complete bipartite graph —
- A graph with two groups of vertices, every possible edge between the groups, and no edges within either group.
- Floor function —
- The function returns the greatest integer no larger than .
- Lower bound —
- A number below which the crossing count of any allowed drawing cannot fall.
Keywords : Crossing number · Harary–Hill formula · Zarankiewicz formula
AI-generated explanation based on the manuscript. Unofficial. Refer to the manuscript for the authoritative version.
3 · Technical details and sources
Claim made in the manuscript (source text)
Resolves the Harary–Hill conjecture and Turán's brickyard problem in the Zarankiewicz formulation, determining the crossing numbers of every complete and complete bipartite graph. The result proves the optimality of the classical drawings among all plane drawings with continuous edge arcs.
Verified by Lean: the Lean software checked the part of the reasoning described below, sometimes only part of the manuscript. This does not mean independent mathematicians have validated the result.
Manuscripts in this family
The crossing number of complete graphs
23/09/2026We prove the Harary–Hill conjecture: for every positive integer n, the ordinary crossing number of the complete graph Kn is
The crossing number of complete bipartite graphs
23/09/2026We prove the Zarankiewicz crossing-number conjecture, resolving Turán's brickyard problem. For all positive integers m, n, the ordinary crossing number of the complete bipartite graph is