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₁ = x₁ and Z_n=Z_n-1x_nZ_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.