{
  "id": "1110.4824",
  "version": "v1",
  "published": "2011-10-21T15:27:27.000Z",
  "updated": "2011-10-21T15:27:27.000Z",
  "title": "Improved lower bounds for the 2-page crossing numbers of K_{m,n} and K_n via semidefinite programming",
  "authors": [
    "Etienne de Klerk",
    "Dmitrii V. Pasechnik"
  ],
  "comment": "20 pages (ignore pages 21 and 22 produced by the arxive.org script, with copies of pictures inserted elsewhere in the text)",
  "journal": "SIAM J. Optim. 22-2 (2012), pp. 581-595",
  "doi": "10.1137/110852206",
  "categories": [
    "math.CO",
    "math.OC"
  ],
  "abstract": "It has been long conjectured that the crossing numbers of the complete bipartite graph K_{m,n} and of the complete graph K_n equal Z(m,n) (the value conjectured by Zarankiewicz, who came up with a drawing reaching this value) and Z(n) :=Z(n,n-2)/4, 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 v_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) v_2(Km,n) =Z(m,n), and (II) v_2(Kn) = Z(n). It is known that (I) holds for min{m, n} <=6, and that (II) holds for n<=14. In this paper we prove that (I) holds asymptotically (that is, lim_n v_2 (K_{m,n})/Z (m, n) = 1) for m=7 and 8. We also prove (II) for 15<=n<=18 and n=20,24, and establish the asymptotic estimate lim_n v_2(K_n)/Z(n) >= 0.9253. The previous best-known lower bound involved the constant 0.8594.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2011-10-21T15:27:27.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C35",
      "90C22"
    ],
    "keywords": [
      "crossing number",
      "semidefinite programming",
      "best-known lower bound",
      "complete bipartite graph",
      "straight line"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 20,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2011arXiv1110.4824D"
    }
  }
}