{
  "id": "1607.07342",
  "version": "v1",
  "published": "2016-07-25T16:22:53.000Z",
  "updated": "2016-07-25T16:22:53.000Z",
  "title": "Packing trees of unbounded degrees in random graphs",
  "authors": [
    "Asaf Ferber",
    "Wojciech Samotij"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "In this paper, we address the problem of packing large trees in $G_{n,p}$. In particular, we prove the following result. Suppose that $T_1, \\dotsc, T_N$ are $n$-vertex trees, each of which has maximum degree at most $(np)^{1/6} / (\\log n)^6$. Then with high probability, one can find edge-disjoint copies of all the $T_i$ in the random graph $G_{n,p}$, provided that $p \\geq (\\log n)^{36}/n$ and $N \\le (1-\\varepsilon)np/2$ for a positive constant $\\varepsilon$. Moreover, if each $T_i$ has at most $(1-\\alpha)n$ vertices, for some positive $\\alpha$, then the same result holds under the much weaker assumptions that $p \\geq (\\log n)^2/(cn)$ and $\\Delta(T_i) \\leq c np / \\log n$ for some~$c$ that depends only on $\\alpha$ and $\\varepsilon$. Our assumptions on maximum degrees of the trees are significantly weaker than those in all previously known approximate packing results.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2016-07-25T16:22:53.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C05",
      "05C80"
    ],
    "keywords": [
      "random graph",
      "unbounded degrees",
      "packing trees",
      "maximum degree",
      "high probability"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}