Given a group G, a set of colors A and a set of forbidden patterns F, the subshift X_F is the set of colorings of G by A that avoid the patterns in F. I recently obtained a simple condition on the set of forbidden patterns F that implies that X_F is nonempty and even provides some lower bound on its growth rate (« the size of X_F »). It seems to be more powerful and it is easier to use than previous results by Aubrun et al.; Bertnshteyn; Miller; Pavlov. Interestingly, the proof of the main theorem relies on a really simple counting argument. This counting argument can be applied to other settings and has been applied to setting where Lovász local lemma, Bertnshteyn cut Lemma and related techniques would usually be applied.
After an introduction, I will present the main result and give the simple proof of the main Lemma behind the result, and then provide some applications to strongly aperiodic subshifts, nonrepetitive subshifts, and Kolmogorov complexity of subshifts. No knowledge of group theory is required (for this result, the argument over Z^2 (the infinite grid) is identical for the more general case and I will focus on this case).
Localisation
Salle de séminaire 4B125 (bâtiment Copernic)
5 Boulevard Descartes 77420 Champs-sur-Marne