Hills 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}lfloorfrac{n}{2}rfloorlfloorfrac{n-1}{2}rfloorlfloorfrac{n-2}{2}rfloorlfloorfrac{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/8pi^2)+O(n^3)$. In analogy with the relation of Moons result to Hills conjecture, Elkies asked if $lim_{ntoinfty} text{cr}_P(K_n)/n^4=1/8pi^2$. We construct drawings of $K_n$ in the projective plane that disprove this.
تحميل البحث