Family 165CombinatoricsLeanNot yet digested

The Harary–Hill and Zarankiewicz crossing-number formulas

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.

Manuscripts in this family · 2

The crossing number of complete graphs

Sep 23, 2026·paper.pdfLean

We prove the Harary–Hill conjecture: for every positive integer n, the ordinary crossing number of the complete graph K

_{n}

\displaystyle \frac14\left\lfloor\frac n2\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.

Full abstract

PDF on GitHub LaTeX source

The crossing number of complete bipartite graphs

Sep 23, 2026·paper.pdfLean

We 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

K_{m,n}

\displaystyle \left\lfloor\frac m2\right\rfloor \left\lfloor\frac{m-1}{2}\right\rfloor \left\lfloor\frac n2\right\rfloor \left\lfloor\frac{n-1}{2}\right\rfloor.

Full abstract

PDF on GitHub LaTeX source