Abstract:

The field of Combinatorics on Words deals with combinatorial problems arising from strings of symbols. One kind of problem is to examine avoidable versus unavoidable regularities in infinite strings from a finite alphabet. For example, Thue showed that using an alphabet of three symbols it is possible to construct an infinite string with no block that is immediately repeated. We say that such a string avoids the pattern xx . On the other hand some patterns, such as xyxzxyx, are unavoidable no matter how many symbols are in the alphabet; in other words, there are always blocks X, Y, Z so that XYXZXYX occur consecutively. There has been recent progress on the intriguing question of determining which patterns can be avoided using what sizes of alphabets.