Improved Bounds for the Crossing Numbers of Km,n and Kn

DOI10.1137/S0895480104442741zbMath1111.05029arXivmath/0404142WikidataQ56874374 ScholiaQ56874374MaRDI QIDQ5470826

John Maharry, Etienne de Klerk, Gelasio Salazar, Dimitrii V. Pasechnik, R. Bruce Richter

Publication date: 1 June 2006

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

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

zbMATH Keywords

semidefinite programmingcopositive coneZarankiewicz conjectureinvariants and centralizer rings of permutation groups

Mathematics Subject Classification ID

Semidefinite programming (90C22) Convex programming (90C25) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Relations of low-dimensional topology with graph theory (57M15) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items

Exploiting group symmetry in semidefinite programming relaxations of the quadratic assignment problem, Reduction of symmetric semidefinite programs using the regular \(\ast\)-representation, A linear programming reformulation of the standard quadratic optimization problem, Rectilinear crossings in complete balanced \(d\)-partite \(d\)-uniform hypergraphs, The smallest mono-unstable convex polyhedron with point masses has 8 faces and 11 vertices, Copositive optimization -- recent developments and applications, Think co(mpletely)positive! Matrix properties, examples and a clustered bibliography on copositive optimization, Symmetric sums of squares over \(k\)-subset hypercubes, The optimal drawings of \(K_{5,n}\), Crossing numbers and stress of random graphs, Using symmetry to optimize over the Sherali-Adams relaxation, The complexity of optimizing over a simplex, hypercube or sphere: a short survey, Crossing number for graphs with bounded pathwidth, A branch-and-cut approach to the crossing number problem, A new branch-and-bound algorithm for standard quadratic programming problems, Unnamed Item, Reduction of truss topology optimization, Numerical block diagonalization of matrix \(\ast\)-algebras with application to semidefinite programming, A Comprehensive Analysis of Polyhedral Lift-and-Project Methods, Invariant Semidefinite Programs, A survey of graphs with known or bounded crossing numbers, Closing in on Hill's Conjecture, Exploiting group symmetry in truss topology optimization, Exploiting special structure in semidefinite programming: a survey of theory and applications, Turán’s Brick Factory Problem: The Status of the Conjectures of Zarankiewicz and Hill