Drawings of complete graphs in the projective plane
Hill's Conjecture states that the crossing number cr(πΎπ) of the complete graph πΎπ in the plane (equivalently, the sphere) is 14βπ2ββπβ12ββπβ22ββπβ32β=π4/64+π(π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 π4/64+π(π3) , thus matching asymptotically the conjectured value of cr(πΎπ) . Let crπ(πΊ) denote the crossing number of a graph πΊ in the projective plane. Recently, Elkies proved that the expected number of crossings in a naturally defined random projective plane drawing of πΎπ is (π4/8π2)+π(π3) . In analogy with the relation of Moon's result to Hill's conjecture, Elkies asked if limπβββcrπ(πΎπ)/π4=1/8π2 . We construct drawings of πΎπ in the projective plane that disprove this.
Wiley