Unavoidable Patterns

As suggested by Currie, we apply the probabilistic method to problems regarding pattern avoidance. Using techniques from analytic combinatorics, we calculate asymptotic pattern occurrence statistics and use them in conjunction with the probabilistic method to establish new results about the Ramsey theory of unavoidable patterns in the full word, partial word, and abelian cases. We suggest additional possible uses of these data in applications such as cryptography and musicology.

Keywords: Ramsey theory; Unavoidable patterns; Combinatorics on words; Partial words; Abelian patterns; Analytic combinatorics; Probabilistic method.