Graph and Matroids Seminar- Anton Bernshteyn

Title: Free subshifts and the Local Lemma

Abstract: The purpose of this talk is to demonstrate how combinatorial tools and techniques can be used to tackle problems in other areas of mathematics, specifically, in topological dynamics. Some of the most important dynamical systems are the so-called subshifts. Roughly speaking, a subshift is a set of infinite "words" over a finite alphabet that is defined by a family of finite "forbidden subwords"; the only subtlety here is that the letters in such a "word" are indexed not by the natural numbers but by the elements of some countable group $\Gamma$. A subshift naturally comes equipped with an action of the group $\Gamma$; for instance, if $\Gamma = \mathbb{Z}$, then the action is given by the formula $(n \cdot w)_i = w_{i + n}$, where $w = (w_i)_{i \in \mathbb{Z}}$ is a word and $n \in \mathbb{Z}$. Glasner and Uspenskij asked whether every countable group admits a nonempty subshift that is free (i.e., such that the stabilizer of every point under the action of $\Gamma$ is trivial). (Incidentally, the existence of a nonempty free subshift for the group $\mathbb{Z}$ follows from an old theorem of Thue.) The positive answer in full generality was obtained by Gao, Jackson, and Seward, who gave a rather technical explicit construction. Later on, Aubrun, Barbieri, and Thomass\'{e} realized that there is a very short and simple probabilistic proof that relies on the Lov\'{a}sz Local Lemma. I will sketch their argument and then explain how the Local Lemma-based approach can be extended to build subshifts that are not just nonempty, but in fact "large" in various senses, answering some open questions raised by Gao, Jackson, and Seward.