{
  "id": "1107.5301",
  "version": "v1",
  "published": "2011-07-26T19:32:00.000Z",
  "updated": "2011-07-26T19:32:00.000Z",
  "title": "Remarks on a Ramsey theory for trees",
  "authors": [
    "János Pach",
    "József Solymosi",
    "Gábor Tardos"
  ],
  "comment": "10 pages 1 figure",
  "categories": [
    "math.CO"
  ],
  "abstract": "Extending Furstenberg's ergodic theoretic proof for Szemer\\'edi's theorem on arithmetic progressions, Furstenberg and Weiss (2003) proved the following qualitative result. For every d and k, there exists an integer N such that no matter how we color the vertices of a complete binary tree T_N of depth N with k colors, we can find a monochromatic replica of T_d in T_N such that (1) all vertices at the same level in T_d are mapped into vertices at the same level in T_N; (2) if a vertex x of T_d is mapped into a vertex y in T_N, then the two children of x are mapped into descendants of the the two children of y in T_N, respectively; and 3 the levels occupied by this replica form an arithmetic progression. This result and its density versions imply van der Waerden's and Szemer\\'edi's theorems, and laid the foundations of a new Ramsey theory for trees. Using simple counting arguments and a randomized coloring algorithm called random split, we prove the following related result. Let N=N(d,k) denote the smallest positive integer such that no matter how we color the vertices of a complete binary tree T_N of depth N with k colors, we can find a monochromatic replica of T_d in T_N which satisfies properties (1) and (2) above. Then we have N(d,k)=\\Theta(dk\\log k). We also prove a density version of this result, which, combined with Szemer\\'edi's theorem, provides a very short combinatorial proof of a quantitative version of the Furstenberg-Weiss theorem.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2011-07-26T19:32:00.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05D10"
    ],
    "keywords": [
      "ramsey theory",
      "complete binary tree",
      "szemeredis theorem",
      "versions imply van der waerdens",
      "extending furstenbergs ergodic theoretic proof"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 10,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2011arXiv1107.5301P"
    }
  }
}