{
  "id": "1701.08335",
  "version": "v1",
  "published": "2017-01-29T00:02:48.000Z",
  "updated": "2017-01-29T00:02:48.000Z",
  "title": "Decomposing the Complete $r$-Graph",
  "authors": [
    "Imre Leader",
    "Luka Milićević",
    "Ta Sheng Tan"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "Let $f_r(n)$ be the minimum number of complete $r$-partite $r$-graphs needed to partition the edge set of the complete $r$-uniform hypergraph on $n$ vertices. Graham and Pollak showed that $f_2(n) = n-1$. An easy construction shows that $f_r(n)\\le (1-o(1))\\binom{n}{\\lfloor r/2\\rfloor}$ and it has been unknown if this upper bound is asymptotically sharp. In this paper we show that $f_r(n)\\le (\\frac{14}{15}+o(1))\\binom{n}{r/2}$ for each even $r\\ge 4$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2017-01-29T00:02:48.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05D05",
      "05C70"
    ],
    "keywords": [
      "uniform hypergraph",
      "upper bound",
      "minimum number",
      "decomposing",
      "edge set"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}