A measurable version of the Lovász Local Lemma

• Gábor Kun (ELTE, Budapest)
• Thursday 24 January 2013, 14:30-15:30
• MR12.

I shall prove a measurable version of the LLL that will allow to prove theorems of the following kind.

Let $G$ be a compact group with a Borel probability measure, and let $S_1, \dots , S_n$ be $k$-element subsets of $G$, where $\frac{2 e n k2}{2k} < 1$ and $\varepsilon > 0$. Then there are measurable subsets $A$ and $B$ of $G$ such that their intersection has measure less than $\varepsilon$, and every shift $gS_i$ of one of the sets intersects both $A$ and $B$.

The measurable LLL requires the same local conditions as the discrete LLL : it gives a measurable colouring (evaluation), but an unfortunate error of measure $\varepsilon$ might occur. I shall apply this measurable LLL to give another solution to the dynamical von Neumann problem of Gaboriau and Lyons. This proof is based on the ideas of the proof of the algorithmic LLL due to Moser and Tardos.

This talk is part of the Combinatorics Seminar series.