In this paper, we use semidefinite programming and representation theory to compute new lower bounds on the crossing number of the complete bipartite graph Km,n , extending a method from de Klerk et al. (SIAM J Discrete Math 20:189–202, 2006) and the subsequent reduction by De Klerk, Pasechnik and Schrijver (Math Prog Ser A and B 109:613–624, 2007). 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 cr (K10,n) ≥ 4.87057 n2- 10 n , cr (K11,n) ≥ 5.99939 n2- 12.5 n , cr (K12,n) ≥ 7.25579 n2- 15 n , cr (K13,n) ≥ 8.65675 n2- 18 n 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.

, , , ,
Mathematical Programming Series A
Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands

Brosch, D., & Polak, S. (2023). New lower bounds on crossing numbers of Km,n from semidefinite programming. Mathematical Programming Series A. doi:10.1007/s10107-023-02028-1