{
  "id": "0911.4982",
  "version": "v1",
  "published": "2009-11-25T23:57:13.000Z",
  "updated": "2009-11-25T23:57:13.000Z",
  "title": "More bounds on the diameters of convex polytopes",
  "authors": [
    "David Bremner",
    "Antoine Deza",
    "William Hua",
    "Lars Schewe"
  ],
  "categories": [
    "math.CO",
    "math.MG"
  ],
  "abstract": "Finding a good bound on the maximal edge diameter $\\Delta(d,n)$ of a polytope in terms of its dimension $d$ and the number of its facets $n$ is one of the basic open questions in polytope theory \\cite{BG}. Although some bounds are known, the behaviour of the function $\\Delta(d,n)$ is largely unknown. The Hirsch conjecture, formulated in 1957 and reported in \\cite{GD}, states that $\\Delta(d,n)$ is linear in $n$ and $d$: $\\Delta(d,n) \\leq n-d$. The conjecture is known to hold in small dimensions, i.e., for $d \\leq 3$ \\cite{VK}, along with other specific pairs of $d$ and $n$ (Table \\ref{before}). However, the asymptotic behaviour of $\\Delta(d,n)$ is not well understood: the best upper bound -- due to Kalai and Kleitman -- is quasi-polynomial \\cite{GKDK}. In this article we will show that $\\Delta(4,12)=7$ and present strong evidence for $\\Delta(5,12)=\\Delta(6,13)=7$. The first of these new values is of particular interest since it indicates that the Hirsch bound is not sharp in dimension 4.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2009-11-25T23:57:13.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "52B05",
      "52B40"
    ],
    "keywords": [
      "convex polytopes",
      "maximal edge diameter",
      "best upper bound",
      "basic open questions",
      "strong evidence"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2009arXiv0911.4982B"
    }
  }
}