Closing in on Hill's Conjecture

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

Bernard Lidický, József Balogh, 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

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

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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\)
• Zarankiewicz's conjecture is finite for each fixed \(m\)
• Minimum Number ofk-Cliques in Graphs with Bounded Independence Number
• On the Crossing Number of Kn 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
• 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 Kn 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 Bipartite Graphs

Cited In (9)

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