Please use this identifier to cite or link to this item: https://hdl.handle.net/10356/96333
 Title: Improved lower bounds for the 2-page crossing numbers of Km,n and Kn via semidefinite programming Authors: Klerk, E. de.Pasechnik, Dmitrii V. Issue Date: 2012 Source: Klerk, E. d. & Pasechnik, D. V. (2012). Improved Lower Bounds for the 2-Page Crossing Numbers of Km,n and Kn via Semidefinite Programming. SIAM Journal on Optimization, 22(2), 581-595. Series/Report no.: SIAM journal on optimization Abstract: 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$. URI: https://hdl.handle.net/10356/96333http://hdl.handle.net/10220/10215 ISSN: 1052-6234 DOI: http://dx.doi.org/10.1137/110852206 Rights: © 2012 Society for Industrial and Applied Mathematics. This paper was published in SIAM Journal on Optimization and is made available as an electronic reprint (preprint) with permission of Society for Industrial and Applied Mathematics. The paper can be found at the following official DOI: [http://dx.doi.org/10.1137/110852206]. One print or electronic copy may be made for personal use only. Systematic or multiple reproduction, distribution to multiple locations via electronic or other means, duplication of any material in this paper for a fee or for commercial purposes, or modification of the content of the paper is prohibited and is subject to penalties under law. Fulltext Permission: open Fulltext Availability: With Fulltext Appears in Collections: SPMS Journal Articles

###### Files in This Item:
File Description SizeFormat
101. Improved lower bounds.pdf256.79 kBAdobe PDF