## Combinatorics Seminar

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

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 Z_{1} = x_{1} and
Z_{n}=Z_{n-1}x_{n}Z_{n-1}.
We study the quantitative aspects of this theorem, showing that there
are extremely long words (whose length is tower function) avoiding
Z_{n}.
Our results are asymptotically tight.
Joint work with David Conlon and Jacob Fox.