Logic Seminar

This talk will focus on the interplay between finite combinatorics and ergodic theory. Consider a free ergodic measure-preserving action $a \colon \Gamma \acts (X,\mu)$ of a countable group $\Gamma$ on a standard probability space $(X, \mu)$. Using a symmetric generating set $S$ for $\Gamma$, one can associate to $a$ a graph $G$ with vertex set $X$ in which two distinct vertices $x$, $y \in X$ are adjacent if and only if they are connected by a group element in $S$ (thus every connected component of $G$ is isomorphic to the Cayley graph of $\Gamma$). It is natural to wonder how combinatorial properties of $G$ interact with ergodic-theoretic properties of $a$. The Lov\'asz Local Lemma, or the~LLL for short, is an important tool in graph theory (and combinatorics in general) that is often used to establish the existence of graph colorings satisfying certain ``local'' constraints. It turns out that if $\Gamma$ is amenable, then the graph $G$ satisfies a measurable analog of the~LLL if and only if $a$ has infinite entropy. In this talk, I will outline the ideas behind the proof of the forward direction of this equivalence, at the heart of which lies the connection between Shannon entropy and Kolmogorov complexity.