论文标题
投影平面中完整图的图纸
Drawings of complete graphs in the projective plane
论文作者
论文摘要
希尔的猜想指出,整个图形的$ \ text {cr}(k_n)$ the Plash the Plane in Plane(等效,球体)是$ \ frac {1} {4} \ lfloor \ frac {n} {2} \ rfloor \ lfloor \ lfloor \ frac {n-1} {2} {2} \ rflo或\ \ lfloor \ frac {n-2} {2} \ rfloor \ lfloor \ frac {n-3} {2} {2} \ rfloor = n^4/64 + o(n^3)$。月亮证明,在球形图中预期的交叉数,在该图形中,该点随机分布和通过大地测量的连接确切地是$ n^4/64+O(n^3)$,因此渐近地匹配了$ \ text {cr}(cr}(k_n)$的猜想值。令$ \ text {cr} _p(g)$表示投影平面中图$ g $的交叉数。最近,Elkies证明了$ k_n $的自然定义随机射击平面图中的预期交叉数为$(n^4/8π^2)+O(n^3)$。与Moon结果与Hill的猜想的关系类似,Elkies问$ \ lim_ {n \ to \ infty} \ text {cr} _p(k_n)/n^4 = 1/8π^2 $。我们在反驳这一示例的平面中构造$ k_n $的图纸。
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π^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π^2$. We construct drawings of $K_n$ in the projective plane that disprove this.