Closing in on Hill's conjecture

DOI10.1137/17M1158859MaRDI QIDQ5232152zbMATH OpenWikidataFDO

Authors József Balogh, Bernard Lidický, Gelasio Salazar

Publication date 29 August 2019

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1711.08958

zbMATH Keywords

complete graphcrossing numberflag algebrasHill's conjecture

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62)

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($K_n$) of the complete graph $K_n$ is $H(n):=frac14lfloorfracn2floorlfloorfracn-12floorlfloorfracn-22floorlfloorfracn-32floor$, for all $nge3$. This has been verified only for $nle12$. 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$(K_n)>0.905,H(n)$. Also using flag algebras, we prove that asymptotically cr$(K_n)$ is at least $0.985,H(n)$. We also show that the spherical geodesic crossing number of $K_n$ is asymptotically at least $0.996,H(n)$.

Recommendations

• Drawings of complete graphs in the projective plane
• Crossing numbers of graphs
• The crossing number of seq-shellable drawings of complete graphs
• Shellable drawings and the cylindrical crossing number of \(K_n\)
• The \(2\)-page crossing number of \(K_n\)

Cites work

• scientific article; zbMATH DE number 3258070 (Why is no real title available?)
• scientific article; zbMATH DE number 3306563 (Why is no real title available?)
• scientific article; zbMATH DE number 3344600 (Why is no real title available?)
• A new lower bound based on Gromov's method of selecting heavily covered points
• A parity theorem for drawings of complete and complete
• Convex drawings of the complete graph: topology meets geometry
• Crossing numbers and combinatorial characterization of monotone drawings of \(K_n\)
• Drawings of \(K_n\) with the same rotation scheme are the same up to Reidemeister moves (Gioan's theorem)
• Flag algebras
• Graph-Theoretic Concepts in Computer Science
• Hypergraphs do jump
• Improved Bounds for the Crossing Numbers of Km,n and Kn
• Improved enumeration of simple topological graphs
• Levi's Lemma, pseudolinear drawings of , and empty triangles
• Limits of order types
• Maximum density of induced 5-cycle is achieved by an iterated blow-up of 5-cycle
• Minimum Number ofk-Cliques in Graphs with Bounded Independence Number
• On crossing numbers of complete tripartite and balanced complete multipartite graphs
• On the Distribution of Crossings in Random Complete Graphs
• On the Minimal Density of Triangles in Graphs
• On the Number of Crossings in a Complete Graph
• On the crossing number of \(K_n\) without computer assistance
• On the crossing number of \(K_{13}\)
• On the number of pentagons in triangle-free graphs
• Rainbow triangles in three-colored graphs
• Reduction of symmetric semidefinite programs using the regular -representation
• Relations Between Crossing Numbers of Complete and Complete Bipartite Graphs
• Shellable drawings and the cylindrical crossing number of \(K_n\)
• Simple realizability of complete abstract topological graphs simplified
• The 2-page crossing number of \(K_{n}\)
• The crossing number of K₁₁ is 100
• The crossing number of K5,n
• The early history of the brick factory problem
• Turán's brick factory problem: the status of the conjectures of Zarankiewicz and Hill
• Zarankiewicz's conjecture is finite for each fixed \(m\)

Cited in

(10)

• A survey of graphs with known or bounded crossing numbers
• Drawings of complete graphs in the projective plane
• On Numerical Invariant of Graph
• Maximum number of almost similar triangles in the plane
• New lower bounds on crossing numbers of \(K_{m,n}\) from semidefinite programming
• Solving Turán's tetrahedron problem for the ℓ2$\ell _2$‐norm
• From art and circuit design to geometry and combinatorics
• The crossing number of seq-shellable drawings of complete graphs
• On the problems of CF-connected graphs
• Convex drawings of the complete graph: topology meets geometry

This page was built for publication: Closing in on Hill's conjecture

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5232152)