New lower bounds on crossing numbers of Km,n from semi definite programming

• 成果类型: Article
• 署名作者: Brosch, Daniel; Polak, Sven C.
• 署名单位: University of Klagenfurt; Tilburg University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-023-02028-1
• 发表日期: 2024
• 页码: 693-715
• 关键词: semidefinite; symmetry

摘要

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,K-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 cr(K-10,K-n) >= 4.87057 n(2)-10n, cr(K-11,K-n) >= 5.99939 n(2)-12.5n, cr (K-12,K-n) >= 7.25579n(2)-15n, cr (K-13,K-n) >= 8.65675 n(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.