{
  "id": "0706.0223",
  "version": "v1",
  "published": "2007-06-01T21:39:34.000Z",
  "updated": "2007-06-01T21:39:34.000Z",
  "title": "Two Erdos problems on lacunary sequences: Chromatic number and Diophantine approximation",
  "authors": [
    "Yuval Peres",
    "Wilhelm Schlag"
  ],
  "comment": "9 pages",
  "doi": "10.1112/blms/bdp126",
  "categories": [
    "math.CO",
    "math.NT"
  ],
  "abstract": "Let ${n_k}$ be an increasing lacunary sequence, i.e., $n_{k+1}/n_k>1+r$ for some $r>0$. In 1987, P. Erdos asked for the chromatic number of a graph $G$ on the integers, where two integers $a,b$ are connected by an edge iff their difference $|a-b|$ is in the sequence ${n_k}$. Y. Katznelson found a connection to a Diophantine approximation problem (also due to Erdos): the existence of $x$ in $(0,1)$ such that all the multiples $n_j x$ are at least distance $\\delta(x)>0$ from the set of integers. Katznelson bounded the chromatic number of $G$ by $Cr^{-2}|\\log r|$. We apply the Lov\\'asz local lemma to establish that $\\delta(x)>cr|\\log r|^{-1}$ for some $x$, which implies that the chromatic number of $G$ is at most $Cr^{-1} |\\log r|$. This is sharp up to the logarithmic factor.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2007-06-01T21:39:34.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C15",
      "42A55",
      "11B05"
    ],
    "keywords": [
      "chromatic number",
      "erdos problems",
      "diophantine approximation problem",
      "lovasz local lemma",
      "katznelson"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 9,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2007arXiv0706.0223P"
    }
  }
}