Improved lower bounds for the 2-page crossing numbers of Km,n and Kn via semidefinite programming

• Main Authors: Klerk, E. de., Pasechnik, Dmitrii V.
• Other Authors: School of Physical and Mathematical Sciences
• Format: Article
• Language: English
• Published: 2013
• Online Access: https://hdl.handle.net/10356/96333; http://hdl.handle.net/10220/10215
• Institution: Nanyang Technological University

It has long been conjectured that the crossing numbers of the complete bipartite graph $K_{m,n}$ and of the complete graph $K_n$ equal $Z(m,n):=\bigl\lfloor\frac{n}{2}\bigr\rfloor \bigl\lfloor\frac{n-1}{2}\bigr\rfloor \bigl\lfloor\frac{m}{2}\bigr\rfloor \bigl\lfloor\frac{m-1}{2}\bigr\rfloor$ and $Z(n):=\frac{1}{4} \bigl\lfloor\frac{n}{2}\bigr\rfloor \bigl\lfloor\frac{n-1}{2}\bigr\rfloor \bigl\lfloor\frac{n-2}{2}\bigr\rfloor \bigl\lfloor\frac{n-3}{2}\bigr\rfloor$, respectively. In a $2$-page drawing of a graph, the vertices are drawn on a straight line (the spine), and each edge is contained in one of the half-planes of the spine. The $2$-page crossing number $\nu_2(G)$ of a graph $G$ is the minimum number of crossings in a $2$-page drawing of $G$. Somewhat surprisingly, there are $2$-page drawings of $K_{m,n}$ (respectively, $K_n$) with exactly $Z(m,n)$ (respectively, $Z(n)$) crossings, thus yielding the conjectures (I) $\nu_2(K_{m,n}) \stackrel{?}{=} Z(m,n)$ and (II) $\nu_2(K_n) \stackrel{?}{=} Z(n)$. It is known that (I) holds for $\min\{m,n\} \le 6$, and that (II) holds for $n \le 14$. In this paper we prove that (I) holds asymptotically (that is, $\lim_{n\to\infty} \nu_2(K_{m,n})/Z(m,n) =1$) for $m=7$ and $8$. We also prove (II) for $15 \le n \le 18$ and $n \in \{20,24\}$, and establish the asymptotic estimate $\lim_{n\to\infty} \nu_2(K_{n})/Z(n) \ge 0.9253.$ The previous best-known lower bound involved the constant $0.8594$.