New lower bounds on crossing numbers of $K_{m,n}$ from semidefinite programming

Abstract

In this paper, we use semidefinite programming and representation theory to compute new lower bounds on the crossing number of the complete bipartite graph $K_{m,n}$, extending a method from de Klerk et al. [SIAM J. Discrete Math. 20 (2006), 189--202] and the subsequent reduction by De Klerk, Pasechnik and Schrijver [Math. Prog. Ser. A and B, 109 (2007) 613--624]. We exploit the full symmetry of the problem using a novel decomposition technique. This results in a full block-diagonalization of the underlying matrix algebra, which we use to improve bounds on several concrete instances. Our results imply that $\text{cr}(K_{10,n})\ge 4.87057n^2-10n$, $\text{cr}(K_{11,n})\ge 5.99939n^2-12.5n$, $\text{cr}(K_{12,n})\ge 7.25579n^2-15n$, $\text{cr}(K_{13,n})\ge 8.65675n^2-18n$ for all $n$. The latter three bounds are computed using a new and well-performing relaxation of the original semidefinite programming bound. This new relaxation is obtained by only requiring one small matrix block to be positive semidefinite.

arXiv comment17 pages, 3 figures, 3 tables. Revisions have been made based on comments of the referees. Accepted for publication in Mathematical Programming