{
  "id": "1709.06163",
  "version": "v1",
  "published": "2017-09-18T20:43:44.000Z",
  "updated": "2017-09-18T20:43:44.000Z",
  "title": "Many Triangles with Few Edges",
  "authors": [
    "R. Kirsch",
    "A. J. Radcliffe"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "Extremal problems concerning the number of independent sets or complete subgraphs in a graph have been well studied in recent years. Cutler and Radcliffe proved that among graphs with $n$ vertices and maximum degree at most $r$, where $n = a(r+1)+b$ and $0 \\le b \\le r$, $aK_{r+1}\\cup K_b$ has the maximum number of complete subgraphs, answering a question of Galvin. Gan, Loh, and Sudakov conjectured that $aK_{r+1}\\cup K_b$ also maximizes the number of complete subgraphs $K_t$ for each fixed size $t \\ge 3$, and proved this for $a = 1$. Cutler and Radcliffe proved this conjecture for $r \\le 6$. We investigate a variant of this problem where we fix the number of edges instead of the number of vertices. We prove that $aK_{r+1}\\cup \\mathcal{ C}(b)$, where $\\mathcal{C}(b)$ is the colex graph on $b$ edges, maximizes the number of triangles among graphs with $m$ edges and any fixed maximum degree $r\\le 8$, where $m = a \\binom{r+1}{2} + b$ and $0 \\le b < \\binom{r+1}{2}$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2017-09-18T20:43:44.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "complete subgraphs",
      "fixed maximum degree",
      "maximum number",
      "independent sets",
      "colex graph"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}