Logic Seminar
Anton Bernshteyn
UIUC
Lovász Local Lemma and measurable combinatorics
Abstract: The Lovász Local Lemma (the LLL for short) is an immensely useful tool in probabilistic combinatorics, introduced by Erd\H{o}s and Lov\'asz in the mid-1970s. Roughly speaking, it says that if certain ``bad'' events are reasonably unlikely and mostly independent from each other, then there is a positive (although typically very small) probability of avoiding all of them at once. The LLL has found a wealth of applications, especially in the study of graph colorings. Following a recent breakthrough of Moser and Tardos, who developed an algorithmic approach to the LLL, a number of effective versions of the LLL have been established. In this talk, I will review the LLL and some of its classical applications, and then talk about recently developed measurable versions of the LLL and their consequences in Borel combinatorics and ergodic theory.
We meet for lunch at noon on the first floor of SEO.
Tuesday April 11, 2017 at 4:00 PM in SEO 427