Drawings of complete graphs in the projective plane

Abstract

Hill's Conjecture states that the crossing number $\text{cr}(K_n)$ of the complete graph $K_n$ in the plane (equivalently, the sphere) is $\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 =n^4/64+O(n^3)$. Moon proved that the expected number of crossings in a spherical drawing in which the points are randomly distributed and joined by geodesics is precisely $n^4/64+O(n^3)$, thus matching asymptotically the conjectured value of $\text{cr}(K_n)$. Let ${\text{cr}}_P(G)$ denote the crossing number of a graph $G$ in the projective plane. Recently, Elkies proved that the expected number of crossings in a naturally defined random projective plane drawing of $K_n$ is $(n^4/8{\pi }^2)+O(n^3)$. In analogy with the relation of Moon's result to Hill's conjecture, Elkies asked if ${\lim }_{n\to \infty }{\text{cr}}_P(K_n)/n^4=1/8{\pi }^2$. We construct drawings of $K_n$ in the projective plane that disprove this.