{
  "id": "1308.3530",
  "version": "v2",
  "published": "2013-08-16T01:01:39.000Z",
  "updated": "2014-09-05T15:25:53.000Z",
  "title": "The number of edges of the edge polytope of a finite simple graph",
  "authors": [
    "Takayuki Hibi",
    "Aki Mori",
    "Hidefumi Ohsugi",
    "Akihiro Shikama"
  ],
  "comment": "10 pages, Major Revision: We replace Section 2 with the results on the asymptotic behavior of $\\mu_d$",
  "categories": [
    "math.CO"
  ],
  "abstract": "Let $[d] = \\{ 1, \\ldots, d \\}$ be the vertex set and $\\Omega_{d}$ the set of finite simple graphs on $[d]$, where $d \\geq 3$. We write $\\varepsilon(G)$ for the number of edges of the edge polytope $\\mathcal{P}_G \\subset {\\mathbb R}^{d}$ of $G \\in \\Omega_{d}$. For example, $\\varepsilon(K_{d}) = d(d-1)(d-2)/2$, where $K_{d}$ is the complete graph on $[d]$. In this paper, we study the number $\\mu_{d} = \\max \\{ \\varepsilon(G) \\, : \\, G \\in \\Omega_{d} \\}$. We show that $\\mu_{d} = \\varepsilon(K_{d})$ for each $3 \\leq d \\leq 14$ and $\\mu_{d} > \\varepsilon(K_{d})$ for each $d \\geq 15$. Moreover, we study the asymptotic behavior of $\\mu_d$. Tuan--Ziegler gave a lower bound for $\\mu_d$ by constructing a random graph. We succeeded in improving this bound by constructing both a non-random graph and a random graph whose complement is bipartite.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2013-08-16T01:01:39.000Z",
      "abstract": "Let $[\\,d\\,] = \\{1, ..., d \\}$ be the vertex set and $\\Omega_{d}$ the set of finite simple graphs on $[\\,d\\,]$, where $d \\geq 3$. We write $\\varepsilon(G)$ for the number of edges of the edge polytope $\\mathcal{P}_G \\subset \\RR^{d}$ of $G \\in \\Omega_{d}$. For example, $\\varepsilon(K_{d}) = d(d-1)(d-2)/2$, where $K_{d}$ is the complete graph on $[\\,d\\,]$. Let $\\mu_{d} = \\max \\{\\varepsilon(G) \\, : \\, G \\in \\Omega_{d} \\}$. We wish to find $G \\in \\Omega_{d}$ with $\\mu_{d} = \\varepsilon(G)$ and to compute $\\mu_{d}$. One may expect $\\mu_{d} = \\varepsilon(K_{d})$. In fact, it turns out to be true that $\\mu_{d} = \\varepsilon(K_{d})$ for each $3 \\leq d \\leq 14$. However, it will be proved that, for each $d \\geq 15$, one has $\\mu_{d} \\geq \\varepsilon(K_d) + 50(d - 14)$. It remains unsolved to find $G \\in \\Omega_{d}$ with $\\mu_{d} = \\varepsilon(G)$ and to compute $\\mu_{d}$ if $d \\geq 15$.",
      "comment": "14 pages",
      "journal": null,
      "doi": null
    },
    {
      "version": "v2",
      "updated": "2014-09-05T15:25:53.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "52B05",
      "05C30"
    ],
    "keywords": [
      "finite simple graph",
      "edge polytope",
      "complete graph",
      "vertex set"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 10,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2013arXiv1308.3530H"
    }
  }
}