{
  "id": "math/0210339",
  "version": "v1",
  "published": "2002-10-22T10:13:11.000Z",
  "updated": "2002-10-22T10:13:11.000Z",
  "title": "Families of trees decompose the random graph in any arbitrary way",
  "authors": [
    "Raphael Yuster"
  ],
  "comment": "20 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "Let $F=\\{H_1,...,H_k\\}$ be a family of graphs. A graph $G$ with $m$ edges is called {\\em totally $F$-decomposable} if for {\\em every} linear combination of the form $\\alpha_1 e(H_1) + ... + \\alpha_k e(H_k) = m$ where each $\\alpha_i$ is a nonnegative integer, there is a coloring of the edges of $G$ with $\\alpha_1+...+\\alpha_k$ colors such that exactly $\\alpha_i$ color classes induce each a copy of $H_i$, for $i=1,...,k$. We prove that if $F$ is any fixed family of trees then $\\log n/n$ is a sharp threshold function for the property that the random graph $G(n,p)$ is totally $F$-decomposable. In particular, if $H$ is a tree, then $\\log n/n$ is a sharp threshold function for the property that $G(n,p)$ contains $\\lfloor e(G)/e(H) \\rfloor$ edge-disjoint copies of $H$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2002-10-22T10:13:11.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C80"
    ],
    "keywords": [
      "random graph",
      "trees decompose",
      "arbitrary way",
      "sharp threshold function",
      "color classes induce"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 20,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2002math.....10339Y"
    }
  }
}