New lower bounds on crossing numbers of K_m,n from semidefinite programming

DOI10.1007/S10107-023-02028-1zbMATH Open1547.05061MaRDI QIDQ6608048FDOQ6608048

Authors Daniel Brosch, Sven C. Polak

Publication date 19 September 2024

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

zbMATH Keywords

semidefinite programmingsymmetry reductioncomplete bipartite graphblock-diagonalizationcrossing numbers

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Semidefinite programming (90C22) Planar graphs; geometric and topological aspects of graph theory (05C10) Combinatorial aspects of representation theory (05E10)

Recommendations

• Reduction of symmetric semidefinite programs using the regular \(\ast\)-representation
• Improved lower bounds for the 2-page crossing numbers of \(K_{m,n}\) and \(K_n\) via semidefinite programming
• On the crossing number of \(K_{m,n}\)
• Improved Bounds for the Crossing Numbers of Km,n and Kn
• Improved lower bounds on book crossing numbers of complete graphs

Cites work

• scientific article; zbMATH DE number 1601795 (Why is no real title available?)
• scientific article; zbMATH DE number 3526920 (Why is no real title available?)
• scientific article; zbMATH DE number 3552764 (Why is no real title available?)
• scientific article; zbMATH DE number 1261512 (Why is no real title available?)
• Algebra of coinvariants and the action of a Coxeter element.
• Closing in on Hill's conjecture
• Crossing Number Problems
• Crossing Number is NP-Complete
• Cyclic‐order graphs and Zarankiewicz's crossing‐number conjecture
• Exploiting symmetry in copositive programs via semidefinite hierarchies
• Improved Bounds for the Crossing Numbers of Km,n and Kn
• New Code Upper Bounds From the Terwilliger Algebra and Semidefinite Programming
• On a problem of P. Turan concerning graphs
• Reduction of symmetric semidefinite programs using the regular \(\ast\)-representation
• Semidefinite Code Bounds Based on Quadruple Distances
• Semidefinite bounds for nonbinary codes based on quadruples
• Strengthened semidefinite programming bounds for codes
• Symmetry groups, semidefinite programs, and sums of squares
• The crossing number of K5,n
• The graph crossing number and its variants: a survey
• Turán's brick factory problem: the status of the conjectures of Zarankiewicz and Hill

This page was built for publication: New lower bounds on crossing numbers of \(K_{m,n}\) from semidefinite programming

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