论文标题
$ k_ {m，n} $的跨越数字的新下限
New lower bounds on crossing numbers of $K_{m,n}$ from semidefinite programming
论文作者
论文摘要
在本文中，我们使用半决赛编程和表示理论来计算完整的双分图$ k_ {m，n} $的交叉数上的新下限，从而扩展了De Klerk等人的方法。 [暹罗J.离散数学。 20（2006），189--202]以及De Klerk，Pasechnik和Schrijver的随后减少。 prog。 ser。 A和B，109（2007）613--624]。我们使用一种新颖的分解技术来利用问题的完全对称性。这导致了基础基质代数的完整块 - 划分，我们用来在几种混凝土实例上改善界限。我们的结果暗示$ \ text {cr}（k_ {10，n}）\ geq 4.87057 n^2-10n $，$ \ text {cr}（k_ {11，n}）\ geq 5.99939 n^2-12.5n $ 15n $，$ \ text {cr}（k_ {13，n}）\ geq 8.65675 n^2-18n $ for All $ n $。后三个界限是使用原始半决赛编程结合的新的良好的放松来计算的。通过仅需要一个小基质块为正半足球，可以获得这种新的放松。
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}) \geq 4.87057 n^2 - 10n$, $\text{cr}(K_{11,n}) \geq 5.99939 n^2-12.5n$, $\text{cr}(K_{12,n}) \geq 7.25579 n^2 - 15n$, $\text{cr}(K_{13,n}) \geq 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.
