Further applications of a power series method for pattern avoidance (Q547794)

Summary: 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.