Drawings of complete graphs in the projective plane. Issue 3 (23rd March 2021)

• Record Type: Journal Article
• Authors: Arroyo, Alan; McQuillan, Dan; Richter, R. Bruce; Salazar, Gelasio; Sullivan, Matthew
• Is Part Of: Journal of graph theory. Volume 97:Issue 3(2021)
• Page Start: 426
• Page End: 440
• Publication Date: 2021-03-23
• Subjects: complete graphs -- crossing number -- projective plane; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.22665
• Languages: English
• ISSNs: 0364-9024

Abstract

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.