New lower bounds on crossing numbers of $$K_{m,n}$$ from semidefinite programming
用半定规划和表示论计算完全二分图K_{m,n}交叉数的下界，改进了之前的方法，给出了K_{10,n}等具体实例的更紧下界。
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}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>K</mml:mi> <mml:mrow> <mml:mi>m</mml:mi> <mml:mo>,</mml:mo> <mml:mi>n</mml:mi> </mml:mrow> </mml:msub> </mml:math> , 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 $$\mathop {\textrm{cr}}\limits (K_{10,n}) \ge 4.87057 n^2 - 10n$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mtext>cr</mml:mtext> <mml:mrow> <mml:mo>(</mml:mo> <mml:msub> <mml:mi>K</mml:mi> <mml:mrow> <mml:mn>10</mml:mn> <mml:mo>,</mml:mo> <mml:mi>n</mml:mi> </mml:mrow> </mml:msub> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>≥</mml:mo> <mml:mn>4.87057</mml:mn> <mml:msup> <mml:mi>n</mml:mi> <mml:mn>2</mml:mn> </mml:msup> <mml:mo>-</mml:mo> <mml:mn>10</mml:mn> <mml:mi>n</mml:mi> </mml:mrow> </mml:math> , $$\mathop {\textrm{cr}}\limits (K_{11,n}) \ge 5.99939 n^2-12.5n$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mtext>cr</mml:mtext> <mml:mrow> <mml:mo>(</mml:mo> <mml:msub> <mml:mi>K</mml:mi> <mml:mrow> <mml:mn>11</mml:mn> <mml:mo>,</mml:mo> <mml:mi>n</mml:mi> </mml:mrow> </mml:msub> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>≥</mml:mo> <mml:mn>5.99939</mml:mn> <mml:msup> <mml:mi>n</mml:mi> <mml:mn>2</mml:mn> </mml:msup> <mml:mo>-</mml:mo> <mml:mn>12.5</mml:mn> <mml:mi>n</mml:mi> </mml:mrow> </mml:math> , $$ \mathop {\textrm{cr}}\limits (K_{12,n}) \ge 7.25579 n^2 - 15n$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mtext>cr</mml:mtext> <mml:mrow> <mml:mo>(</mml:mo> <mml:msub> <mml:mi>K</mml:mi> <mml:mrow> <mml:mn>12</mml:mn> <mml:mo>,</mml:mo> <mml:mi>n</mml:mi> </mml:mrow> </mml:msub> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>≥</mml:mo> <mml:mn>7.25579</mml:mn> <mml:msup> <mml:mi>n</mml:mi> <mml:mn>2</mml:mn> </mml:msup> <mml:mo>-</mml:mo> <mml:mn>15</mml:mn> <mml:mi>n</mml:mi> </mml:mrow> </mml:math> , $$\mathop {\textrm{cr}}\limits (K_{13,n}) \ge 8.65675 n^2-18n$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mtext>cr</mml:mtext> <mml:mrow> <mml:mo>(</mml:mo> <mml:msub> <mml:mi>K</mml:mi> <mml:mrow> <mml:mn>13</mml:mn> <mml:mo>,</mml:mo> <mml:mi>n</mml:mi> </mml:mrow> </mml:msub> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>≥</mml:mo> <mml:mn>8.65675</mml:mn> <mml:msup> <mml:mi>n</mml:mi> <mml:mn>2</mml:mn> </mml:msup> <mml:mo>-</mml:mo> <mml:mn>18</mml:mn> <mml:mi>n</mml:mi> </mml:mrow> </mml:math> 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.