Pattern occurrence statistics and applications to the Ramsey theory of unavoidable patterns

Jim Tao1
1Department of Mathematics, Caltech MC 253-37, 1200 E California Blvd, Pasadena, California 91125, USA

Abstract

As suggested by Currie, we apply the probabilistic method to problems regarding pattern avoidance. Using techniques from analytic combinatorics, we calculate asymptotic mean pattern occurrence and use them in  conjunction with the probabilistic method to establish new results about the Ramsey theory of unavoidable  patterns in the abelian full word case and in the nonabelian partial word case.

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