Skip to main content
Article
Closing in on Hill's conjecture
SIAM Journal on Discrete Mathematics
  • József Balogh, University of Illinois at Urbana-Champaign
  • Bernard Lidický, Iowa State University
  • Gelasio Salazar, Universidad Autonoma de San Luis Potosi
Document Type
Article
Publication Version
Published Version
Publication Date
1-1-2019
DOI
10.1137/17M1158859
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) := 1 4 \lfloor n 2 \rfloor \lfloor n 1 2 \rfloor \lfloor n 2 2 \rfloor \lfloor n 3 2 \rfloor 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.905H(n). Also using this framework, 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 article is published as Balogh, József, Bernard Lidický, and Gelasio Salazar. "Closing in on Hill's Conjecture." SIAM Journal on Discrete Mathematics 33, no. 3 (2019): 1261-1276. doi: 10.1137/17M1158859. Posted with permission.

Copyright Owner
Society for Industrial and Applied Mathematics
Language
en
File Format
application/pdf
Citation Information
József Balogh, Bernard Lidický and Gelasio Salazar. "Closing in on Hill's conjecture" SIAM Journal on Discrete Mathematics Vol. 33 Iss. 3 (2019) p. 1261 - 1276
Available at: http://works.bepress.com/bernard-lidicky/45/