Further applications of a power series method for pattern avoidance
The electronic journal of combinatorics, Tome 18 (2011) 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 $x$ of $w$ and no non-erasing morphism $h$ from $\Delta^*$ to $\Sigma^*$ such that $h(p) = x$. Bell and Goh have recently applied an algebraic technique due to Golod to show that for a certain wide class of patterns $p$ there are exponentially many words of length $n$ over a $4$-letter alphabet that avoid $p$. We consider some further consequences of their work. In particular, we show that any pattern with $k$ variables of length at least $4^k$ is avoidable on the binary alphabet. This improves an earlier bound due to Cassaigne and Roth.
@article{10_37236_621,
author = {Narad Rampersad},
title = {Further applications of a power series method for pattern avoidance},
journal = {The electronic journal of combinatorics},
year = {2011},
volume = {18},
number = {1},
doi = {10.37236/621},
zbl = {1219.68128},
url = {http://geodesic.mathdoc.fr/articles/10.37236/621/}
}
Narad Rampersad. Further applications of a power series method for pattern avoidance. The electronic journal of combinatorics, Tome 18 (2011) no. 1. doi: 10.37236/621
Cité par Sources :