Campus Units

Mathematics

Document Type

Article

Publication Version

Submitted Manuscript

Publication Date

11-24-2017

Journal or Book Title

arxiv

Abstract

Borrowing Laszlo Szekely's lively expression, we show that Hill's conjecture is "asymptotically at least 98.5% true". This long-standing conjecture states that the crossing number cr(Kn) of the complete graph Kn is H(n):=14⌊n2⌋⌊n−12⌋⌊n−22⌋⌊n−32⌋, for all n≥3. This has been verified only for n≤12. Using flag algebras, Norin and Zwols obtained the best known asymptotic lower bound for the crossing number of complete bipartite graphs, from which it follows that for every sufficiently large n, cr(Kn)>0.905H(n). Also using flag algebras, we prove that asymptotically cr(Kn) is at least 0.985H(n). We also show that the spherical geodesic crossing number of Kn is asymptotically at least 0.996H(n).

Comments

This is a manuscript made available through arxiv: https://arxiv.org/abs/1711.08958.

Copyright Owner

The Authors

Language

en

File Format

application/pdf

Share

COinS