2020/09/07 by Bojan Mohar, Mohar, Bojan
Computer Science · Mathematics · #05C10 #68R10 #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #Point processes and geometric inequalities #Topological and Geometric Data Analysis #math.CO #msc:05C10 #msc:68R10
paper · pdf · doi:10.48550/arxiv.2009.03418
6 pages
arxiv created 2020/09/07 · openalex publication_date 2020/09/07 · arxiv updated 2020/09/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In the 1950's, English painter Anthony Hill described drawings of complete graphs Kn in the plane having precisely H(n) = \tfrac14\lfloor \tfracn2\rfloor \lfloor \tfracn-12\rfloor \lfloor \tfracn-22\rfloor \lfloor \tfracn-32\rfloor crossings. It became a conjecture that this number is minimum possible and, despite serious efforts, the conjecture is still widely open. Another way of drawing Kn with the same number of crossings was found by Blažek and Koman in 1963. In this note we provide, for the first time, a very general construction of drawings attaining the same bound. Surprisingly, the proof is extremely short and may as well qualify as a "book proof". In particular, it gives a very simple explanation of the phenomenon discovered by Moon in 1968 that a random set of n points on the unit sphere \SS2 in \RR3 joined by geodesics gives rise to a drawing whose number of crossings asymptotically approaches the Hill value H(n).