Event Detail

The Lovász Local Lemma is an important tool in probabilistic combinatorics. Roughly speaking, it shows the existence of a function satisfying certain combinatorial constraints by checking a set of numerical conditions. In addition to its importance in combinatorics, the Local Lemma has recently found applications in many other fields, such as ergodic theory. In this talk, we address the following question: When can we choose the function whose existence is guaranteed by the Local Lemma to be Borel? Csóka, Grabowski, Máthé, Pikhurko, and Tyros proved a Borel version of the Local Lemma under the assumption that a certain auxiliary graph is of subexponential growth. Unfortunately, their proof only works when the range of the desired function is finite. Using a different approach, we extend their result to the case of continuous range as well as to graphs of limited exponential growth. This is joint work with Jing Yu.