Further applications of a power series method for pattern avoidance (Q547794)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Further applications of a power series method for pattern avoidance |
scientific article |
Statements
Further applications of a power series method for pattern avoidance (English)
0 references
24 June 2011
0 references
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.
0 references
binary alphabet
0 references