Closing in on Hill's conjecture

Abstract

Borrowing László Székely's lively expression, we show that Hill's conjecture is "asymptotically at least 98.5% true". This long-standing conjecture states that the crossing number cr($K_n$) of the complete graph $K_n$ is $H(n):=\frac{1}{4}\lfloor \frac{n}{2}\rfloor \lfloor \frac{n-1}{2}\rfloor \lfloor \frac{n-2}{2}\rfloor \lfloor \frac{n-3}{2}\rfloor$, for all $n\ge 3$. This has been verified only for $n\le 12$. Using flag algebras, Norin and Zwols obtained the best known asymptotic lower bound for the crossing number of complete bipartite graphs, from which it follows that for every sufficiently large $n$, cr$(K_n)>0.905H(n)$. Also using flag algebras, we prove that asymptotically cr$(K_n)$ is at least $0.985H(n)$. We also show that the spherical geodesic crossing number of $K_n$ is asymptotically at least $0.996H(n)$.

20 pages, 5 figures, fixed remarks from referees

Cited by in corpus (2)

• Solving Turán's Tetrahedron Problem for the ${\ell }_2$-Norm
• Maximum Number of Almost Similar Triangles in the Plane