@article{db1ceaeb03f04729b3a22097909cd7bd,
title = "Closing in on Hill's conjecture",
abstract = "Borrowing L\'aszl\'o Sz\'ekely'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 (formula presented) for all n \geq 3. This has been verified only for n \leq 12. Using the flag algebra framework, 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.905 H(n). Also using this framework, we prove that asymptotically cr(Kn) is at least 0.985 H(n). We also show that the spherical geodesic crossing number of Kn is asymptotically at least 0.996 H(n).",
keywords = "Complete graph, Crossing number, Flag algebras, Hill's conjecture",
author = "J{\'o}zsef Balogh and Bernard Lidick{\'y} and Gelasio Salazar",
note = "Funding Information: \ast Received by the editors November 27, 2017; accepted for publication (in revised form) April 23, 2019; published electronically July 18, 2019. https://doi.org/10.1137/17M1158859 Funding: The first author's research was partially supported by NSF grant DMS-1500121 and the Langan Scholar Fund (UIUC). The second author's research was supported in part by NSF grant DMS-1600390. The third author's research was supported by CONACYT grant 222667. \dagger Department of Mathematical Sciences, University of Illinois at Urbana-Champaign, Urbana, IL 61801 (
[email protected]). \ddagger Department of Mathematics, Iowa State University, Ames, IA 50011 (
[email protected]). \S Instituto de F\{\i'}sica, Universidad Aut\o'noma de San Luis Potos\{\'i}, San Luis Potos\{\'i}, Mexico (
[email protected]). Funding Information: The first author's research was partially supported by NSF grant DMS-1500121 and the Langan Scholar Fund (UIUC). The second author's research was supported in part by NSF grant DMS-1600390. The third author's research was supported by CONACYT grant 222667. We thank Oswin Aichholzer for making available to us the collection \scrM 6 and for checking that our collection \scrM 7 agrees with the one previously found by him. This helped us verify our findings for the collections \scrE 6 and \scrE 7, as described in section 4. We also thank Carolina Medina and the anonymous referees for helpful comments. Publisher Copyright: {\textcopyright} 2019 Society for Industrial and Applied Mathematics Copyright: Copyright 2019 Elsevier B.V., All rights reserved.",
year = "2019",
doi = "10.1137/17M1158859",
language = "English (US)",
volume = "33",
pages = "1261--1276",
journal = "SIAM Journal on Discrete Mathematics",
issn = "0895-4801",
publisher = "Society for Industrial and Applied Mathematics Publications",
number = "3",
}