Drawings of complete graphs in the projective plane. Issue 3 (23rd March 2021) - Arroyo, Alan; McQuillan, Dan; Richter, R. Bruce; Salazar, Gelasio; Sullivan, Matthew
Abstract: Hill's Conjecture states that the crossing number cr ( K n ) of the complete graph K n in the plane (equivalently, the sphere) is 1 4 ⌊ n 2 ⌋ ⌊ n − 1 2 ⌋ ⌊ n − 2 2 ⌋ ⌊ n − 3 2 ⌋ = 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 cr ( K n ) . Let 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 π 2 ) + O ( n 3 ) . In analogy with the relation of Moon's result to Hill's conjecture, Elkies asked if lim n → ∞   cr P ( K n ) ∕ n 4 = 1 ∕ 8 π 2 . We construct drawings of K n in the projective plane that disprove this.