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/96333
http://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 PDFThumbnail
View/Open

Google ScholarTM

Check

Altmetric

Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.