IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

Bounds on Zimin Word Avoidance

  • Nov. 25, 2013
  • 3:15 p.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 explore bounds on 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