In combinatorics on words, a word $w$ over an alphabet $\Sigma$ is said to avoid a pattern $p$ over an alphabet $\Delta$ if there is no factor $f$ of $w$ such that $f= h(p)$ where $h: \Delta^*\to\Sigma^*$ is a non-erasing morphism. A pattern $p$ is said to be $k$-avoidable if there exists an infinite word over a $k$-letter alphabet that avoids $p$. We give a positive answer to Problem 3.3.2 in Lothaire's book "Algebraic combinatorics on words'", that is, every pattern with $k$ variables of length at least $2^k$ (resp. $3\times2^{k-1}$) is 3-avoidable (resp. 2-avoidable). This conjecture was first stated by Cassaigne in his thesis in 1994. This improves previous bounds due to Bell and Goh, and Rampersad.
@article{10_37236_3038,
author = {Pascal Ochem and Alexandre Pinlou},
title = {Application of entropy compression in pattern avoidance},
journal = {The electronic journal of combinatorics},
year = {2014},
volume = {21},
number = {2},
doi = {10.37236/3038},
zbl = {1299.68046},
url = {http://geodesic.mathdoc.fr/articles/10.37236/3038/}
}
TY - JOUR
AU - Pascal Ochem
AU - Alexandre Pinlou
TI - Application of entropy compression in pattern avoidance
JO - The electronic journal of combinatorics
PY - 2014
VL - 21
IS - 2
UR - http://geodesic.mathdoc.fr/articles/10.37236/3038/
DO - 10.37236/3038
ID - 10_37236_3038
ER -
%0 Journal Article
%A Pascal Ochem
%A Alexandre Pinlou
%T Application of entropy compression in pattern avoidance
%J The electronic journal of combinatorics
%D 2014
%V 21
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/3038/
%R 10.37236/3038
%F 10_37236_3038
Pascal Ochem; Alexandre Pinlou. Application of entropy compression in pattern avoidance. The electronic journal of combinatorics, Tome 21 (2014) no. 2. doi: 10.37236/3038
