Closing in on Hill's conjecture

DOI10.1137/17M1158859zbMATH Open1419.05050arXiv1711.08958WikidataQ123149958 ScholiaQ123149958MaRDI QIDQ5232152FDOQ5232152

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)

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

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

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

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)

Cites Work

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

Cited In (10)

• Drawings of complete graphs in the projective plane
• On Numerical Invariant of Graph
• New lower bounds on crossing numbers of \(K_{m,n}\) from semidefinite programming
• Maximum number of almost similar triangles in the plane
• 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
• A survey of graphs with known or bounded crossing numbers

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)