Closing in on Hill's conjecture
Article

 Overview

 Research

 Identity

 Additional Document Info

 View All

Overview
abstract

Borrowing L\%27aszl\%27o Sz\%27ekely%27s lively expression, we show that Hill%27s conjecture is ``asymptotically at least 98.5\%25 true. This longstanding 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). © 2019 Society for Industrial and Applied Mathematics

Borrowing L\'aszl\'o Sz\'ekely's lively expression, we show that Hill's conjecture is ``asymptotically at least 98.5\%25 true. This longstanding 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). © 2019 Society for Industrial and Applied Mathematics
publication date
funding provided via
published in
Research
keywords

Complete graph; Crossing number; Flag algebras; Hill's conjecture Algebra; Complete bipartite graphs; Complete graphs; Crossing number; Hill's conjecture; Large N; Lower bounds; Graph theory
Identity
Digital Object Identifier (DOI)
Additional Document Info
start page
end page
volume
issue