{
  "id": "2206.02755",
  "version": "v1",
  "published": "2022-06-06T17:31:34.000Z",
  "updated": "2022-06-06T17:31:34.000Z",
  "title": "New lower bounds on crossing numbers of $K_{m,n}$ from permutation modules and semidefinite programming",
  "authors": [
    "Daniel Brosch",
    "Sven Polak"
  ],
  "comment": "15 pages, 3 figures, 3 tables",
  "categories": [
    "math.CO",
    "cs.DM",
    "math.OC",
    "math.RT"
  ],
  "abstract": "In this paper, we use semidefinite programming and representation theory to compute new lower bounds on the crossing number of the complete bipartite graph $K_{m,n}$, extending a method from de Klerk et al. [SIAM J. Discrete Math. 20 (2006), 189-202] and the subsequent reduction by De Klerk, Pasechnik and Schrijver [Math. Prog. Ser. A and B, 109 (2007) 613-624]. We exploit the full symmetry of the problem by developing a block-diagonalization of the underlying matrix algebra and use it to improve bounds on several concrete instances. Our results imply that $\\text{cr}(K_{10,n}) \\geq 4.87057 n^2 - 10n$, $\\text{cr}(K_{11,n}) \\geq 5.99939 n^2-12.5n$, $ \\text{cr}(K_{12,n}) \\geq 7.25579 n^2 - 15n$, $\\text{cr}(K_{13,n}) \\geq 8.65675 n^2-18n$ for all $n$. The latter three bounds are computed using a new relaxation of the original semidefinite programming bound, by only requiring one small matrix block to be positive semidefinite. Our lower bound on $K_{13,n}$ implies that for each fixed $m \\geq 13$, $\\lim_{n \\to \\infty} \\text{cr}(K_{m,n})/Z(m,n) \\geq 0.8878 m/(m-1)$. Here $Z(m,n)$ is the Zarankiewicz number: the conjectured crossing number of $K_{m,n}$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2022-06-06T17:31:34.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C10",
      "68R10",
      "90C22",
      "05E10"
    ],
    "keywords": [
      "lower bound",
      "crossing number",
      "permutation modules",
      "complete bipartite graph",
      "original semidefinite programming bound"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 15,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}