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
    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

    Identifiers