Building large free subshifts using the Local Lemma

  • Anton Bernshteyn

    University of Illinois at Urbana-Champaign, USA and Carnegie Mellon University, Pittsburgh, USA
Building large free subshifts using the Local Lemma cover
Download PDF

A subscription is required to access this article.

Abstract

Gao, Jackson, and Seward [12] proved that every countably infinite group admits a nonempty free subshift . Here we strengthen this result by showing that free subshifts can be "large" in various senses. Specifically, we prove that for any and , there exists a free subshift of Hausdorff dimension and, if is sofic, entropy at least , answering two questions attributed by Gao, Jackson, and Seward to Juan Souto [13]. Furthermore, we establish a general lower bound on the largest "size" of a free subshift contained inside a given subshift . A central role in our arguments is played the Lovász Local Lemma, an important tool in probabilistic combinatorics, whose relevance to the problem of finding free subshifts was first recognized by Aubrun, Barbieri, and Thomassé [3].

Cite this article

Anton Bernshteyn, Building large free subshifts using the Local Lemma. Groups Geom. Dyn. 13 (2019), no. 4, pp. 1417–1436

DOI 10.4171/GGD/528