IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

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.

© Interdisciplinary Mathematics Institute | The University of South Carolina Board of Trustees | Webmaster
USC