{
  "id": "math/0404142",
  "version": "v1",
  "published": "2004-04-06T21:03:11.000Z",
  "updated": "2004-04-06T21:03:11.000Z",
  "title": "Improved bounds for the crossing numbers of K_m,n and K_n",
  "authors": [
    "E. de Klerk",
    "J. Maharry",
    "D. V. Pasechnik",
    "R. B. Richter",
    "G. Salazar"
  ],
  "comment": "LaTeX, 18 pages, 2 figures",
  "journal": "SIAM J. Discr. Math. 20(2006), 189--202",
  "doi": "10.1137/S0895480104442741",
  "categories": [
    "math.CO",
    "math.OC"
  ],
  "abstract": "It has been long--conjectured that the crossing number cr(K_m,n) of the complete bipartite graph K_m,n equals the Zarankiewicz Number Z(m,n):= floor((m-1)/2) floor(m/2) floor((n-1)/2) floor(n/2). Another long--standing conjecture states that the crossing number cr(K_n) of the complete graph K_n equals Z(n):= floor(n/2) floor((n-1)/2) floor((n-2)/2) floor((n-3)/2)/4. In this paper we show the following improved bounds on the asymptotic ratios of these crossing numbers and their conjectured values: (i) for each fixed m >= 9, lim_{n->infty} cr(K_m,n)/Z(m,n) >= 0.83m/(m-1); (ii) lim_{n->infty} cr(K_n,n)/Z(n,n) >= 0.83; and (iii) lim_{n->infty} cr(K_n)/Z(n) >= 0.83. The previous best known lower bounds were 0.8m/(m-1), 0.8, and 0.8, respectively. These improved bounds are obtained as a consequence of the new bound cr(K_{7,n}) >= 2.1796n^2 - 4.5n. To obtain this improved lower bound for cr(K_{7,n}), we use some elementary topological facts on drawings of K_{2,7} to set up a quadratic program on 6! variables whose minimum p satisfies cr(K_{7,n}) >= (p/2)n^2 - 4.5n, and then use state--of--the--art quadratic optimization techniques combined with a bit of invariant theory of permutation groups to show that p >= 4.3593.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2004-04-06T21:03:11.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C10",
      "05C62",
      "90C22",
      "90C25",
      "57M15",
      "68R10"
    ],
    "keywords": [
      "crossing number",
      "state-of-the-art quadratic optimization techniques",
      "lower bound",
      "complete bipartite graph",
      "invariant theory"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "LaTeX",
      "pages": 18,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2004math......4142D"
    }
  }
}