Algorithms, Combinatorics and Optimization Seminar Anton Bernshteyn
UIUC
Title: Lovász Local Lemma and measurable graph colorings (ACO/Logic seminar)

Abstract: The Lovász Local Lemma, or the LLL for short, is an immensely important tool in probabilistic combinatorics. It is typically used to demonstrate the existence of a function f: X $ \rightarrow$ Y satisfying certain "local" combinatorial constraints, where X is an underlying combinatorial structure (e.g. a graph) and Y is a (usually finite) set (e.g. a set of colors). Since its first appearance in 1975, the LLL found numerous applications in combinatorics, some of them straightforward, and some highly technical and sophisticated. In this talk, we will consider the following question: Assume X is equipped with a standard Borel structure and a probability Borel measure $\mu$. Can the function f, whose existence is asserted by the LLL, be $\mu$-measurable? Most of our attention will be focused on the situation when the combinatorial structure on X is in some sense "induced" by a measure-preserving action of a countable group $\mathit{ \Gamma}$. We will see that for some actions the answer is positive (which yields measurable analogs of various combinatorial consequences of the LLL for such actions). On the other hand, for some actions the measurable version of the LLL fails; in fact, if $\mathit{ \Gamma}$ is amenable, then a probability measure-preserving action of $\mathit{ \Gamma}$ satisfies a measurable analog of the LLL if and only if it has infinite entropy.

Date: Tuesday, October 11, 2016
Time: 3:30 pm
Location: Wean Hall 8220
Note: unusual day