A simple counting argument applied to lower bounds on the growth of subshifts
Time: 14:00 -- Location: LRI, 445
summary: 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.; Bernshteyn; 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, Bernshteyn cut Lemma and related techniques would usually be applied. After an introduction, I will present the main result and then provide some applications to strongly aperiodic subshifts, nonrepetitive subshifts, and Kolmogorov complexity of subshifts. I will then give the simple proof of the main Lemma behind the result.