Lukasz Grabowski: Borel Local Lemma

Lovasz' Local Lemma is one of the most widely used tools in combinatorics and its applications. Given a graph G let us fix for each vertex v of G a set B(v) of "local forbidden colorings", i.e. B(v) is a set of 0/1 colorings of the neighbourhood of v. The local lemma gives a condition under which a "good coloring" of the vertices of G exists, i.e. a coloring f such that for each vertex v the restriction of f to the neighbourhood of v is not forbidden. We prove a Borel version of the local lemma: when G is a Borel graph of subexponential growth and the sets B(v) of forbidden configurations are chosen in a Borel way, then there exists a good coloring which is a Borel function. If G is a graphing associated to a p.m.p. action of a finitely generated amenable group then we are able to show somewhat less: there exists a good coloring which is a measurable function. The main tool which we develop, which is of independent interest, is a new version of the Moser-Tardos algorithm, where random bits used to resample a coloring no longer need to be chosen independently. Joint work with E. Csoka, A. Mathe, O. Pikhurko and K. Tyros.