Doubled patterns are 3-avoidable
The electronic journal of combinatorics, Tome 23 (2016) no. 1
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$. A pattern is said to be doubled if no variable occurs only once. Doubled patterns with at most 3 variables and doubled patterns with at least 6 variables are $3$-avoidable. We show that doubled patterns with 4 and 5 variables are also $3$-avoidable.
@article{10_37236_5618,
author = {Pascal Ochem},
title = {Doubled patterns are 3-avoidable},
journal = {The electronic journal of combinatorics},
year = {2016},
volume = {23},
number = {1},
doi = {10.37236/5618},
zbl = {1335.68191},
url = {http://geodesic.mathdoc.fr/articles/10.37236/5618/}
}
Pascal Ochem. Doubled patterns are 3-avoidable. The electronic journal of combinatorics, Tome 23 (2016) no. 1. doi: 10.37236/5618
Cité par Sources :