Closing in on Hill's conjecture

József Balogh, Bernard Lidický, Gelasio Salazar

Research output: Contribution to journalArticlepeer-review

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).

Original languageEnglish (US)
Pages (from-to)1261-1276
Number of pages16
JournalSIAM Journal on Discrete Mathematics
Volume33
Issue number3
DOIs
StatePublished - 2019

Keywords

  • Complete graph
  • Crossing number
  • Flag algebras
  • Hill's conjecture

ASJC Scopus subject areas

  • Mathematics(all)

Fingerprint

Dive into the research topics of 'Closing in on Hill's conjecture'. Together they form a unique fingerprint.

Cite this