Combinatorics Seminar

When: Sunday, January 7, 10am
Where: Schreiber 309
Speaker: Benny Sudakov, ETH
Title: Unavoidable patterns in words


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 proved Ramsey theorem for words. They 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 Z1 = x1 and Zn=Zn-1xnZn-1.

We study the quantitative aspects of this theorem, showing that there are extremely long words (whose length is tower function) avoiding Zn. Our results are asymptotically tight.

Joint work with David Conlon and Jacob Fox.