{
  "id": "1605.04877",
  "version": "v1",
  "published": "2016-05-16T19:27:09.000Z",
  "updated": "2016-05-16T19:27:09.000Z",
  "title": "Borel version of the Local Lemma",
  "authors": [
    "Endre Csóka",
    "Łukasz Grabowski",
    "András Máthé",
    "Oleg Pikhurko",
    "Konstantinos Tyros"
  ],
  "comment": "26 pages",
  "categories": [
    "math.CO",
    "math.DS",
    "math.PR"
  ],
  "abstract": "We prove a Borel version of the local lemma, i.e. we show that, under suitable assumptions, if the set of variables in the local lemma has a structure of a Borel space, then there exists a satisfying assignment which is a Borel function. The main tool which we develop for the proof, which is of independent interest, is a parallel version of the Moser-Tardos algorithm which uses the same random bits to resample clauses that are far enough in the dependency graph.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2016-05-16T19:27:09.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "local lemma",
      "borel version",
      "borel function",
      "dependency graph",
      "borel space"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 26,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}