{
  "id": "0906.3530",
  "version": "v1",
  "published": "2009-06-18T21:02:15.000Z",
  "updated": "2009-06-18T21:02:15.000Z",
  "title": "Decompositions into subgraphs of small diameter",
  "authors": [
    "Jacob Fox",
    "Benny Sudakov"
  ],
  "comment": "18 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "We investigate decompositions of a graph into a small number of low diameter subgraphs. Let P(n,\\epsilon,d) be the smallest k such that every graph G=(V,E) on n vertices has an edge partition E=E_0 \\cup E_1 \\cup ... \\cup E_k such that |E_0| \\leq \\epsilon n^2 and for all 1 \\leq i \\leq k the diameter of the subgraph spanned by E_i is at most d. Using Szemer\\'edi's regularity lemma, Polcyn and Ruci\\'nski showed that P(n,\\epsilon,4) is bounded above by a constant depending only \\epsilon. This shows that every dense graph can be partitioned into a small number of ``small worlds'' provided that few edges can be ignored. Improving on their result, we determine P(n,\\epsilon,d) within an absolute constant factor, showing that P(n,\\epsilon,2) = \\Theta(n) is unbounded for \\epsilon < 1/4, P(n,\\epsilon,3) = \\Theta(1/\\epsilon^2) for \\epsilon > n^{-1/2} and P(n,\\epsilon,4) = \\Theta(1/\\epsilon) for \\epsilon > n^{-1}. We also prove that if G has large minimum degree, all the edges of G can be covered by a small number of low diameter subgraphs. Finally, we extend some of these results to hypergraphs, improving earlier work of Polcyn, R\\\"odl, Ruci\\'nski, and Szemer\\'edi.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2009-06-18T21:02:15.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C12",
      "05C35",
      "05C65",
      "05C40"
    ],
    "keywords": [
      "small diameter",
      "low diameter subgraphs",
      "small number",
      "decompositions",
      "szemeredis regularity lemma"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 18,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2009arXiv0906.3530F"
    }
  }
}