Oct. 11, 3:30pm, Wean 8220 (Note unusual day)

Anton Bernshteyn, UIUC

Lovász Local Lemma and measurable graph colorings (ACO/Logic seminar)

Anton Bernshteyn, UIUC

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* → *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 μ. Can the function *f*, whose
existence is asserted by the LLL, be μ-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 *Γ*. 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 *Γ* is
amenable, then a probability measure-preserving action of *Γ*
satisfies a measurable analog of the LLL if and only if it has infinite
entropy.