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.