Talks

Spring 2017

# Unavoidable Patterns in Words

Friday, April 14th, 2017 9:30 am – 10:30 am

Event:

Speaker:

A word w is said to contain the pattern P if there is a way to substitute a nonempty word for each letter in P so that the resulting word is a subword of w. Bean, Ehrenfeucht and McNulty and, independently, Zimin characterised the patterns P which are unavoidable, in the sense that any sufficiently long word over a fixed alphabet contains P. Zimin's characterisation says that a pattern is unavoidable if and only if it is contained in a Zimin word, where the Zimin words are defined by Z_1 = x_1 and Z_n=Z_{n-1} x_n Z_{n-1}. We study the quantitative aspects of this theorem, obtaining essentially tight tower-type bounds for the function f(n,q), the least integer such that any word of length f(n, q) over an alphabet of size q contains Z_n.

Joint work with Jacob Fox and Benny Sudakov.