## Probabilistic Bounds on Zimin Word Avoidance

- March 21, 2014
- 11 a.m.
- LeConte 312

## Abstract

Word $W$ witnesses word $V$ provided there is a homomorphism $\phi$ defined by mapping letters to words such that $\phi(V)$ is a subword of $W$. Otherwise, $W$ is said to avoid $V$. If on any arbitrary finite alphabet, there are finitely many words that avoid $V$, then we say $V$ is unavoidable. Zimin (1982) proved that every unavoidable word is witnessed by some word $Z _ n$, defined by: $Z _ 1 = u _ 1$ and $Z _ {n+1} = Z _ nu _ {n+1}Z _ n$. Today we use the probabilistic method to bound how long words can be and still avoid the unavoidable Zimin words.