IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

Doubled-Word Density Distribution

  • April 17, 2015
  • 2:30 p.m.
  • LeConte 312

Abstract

$W$ is said to \emph{encounter} word $V$ provided there is a homomorphism $\phi$ mapping letters to nonempty words so that $\phi(V)$ is a substring of $W$. For example, taking $\phi$ such that $\phi(e)=co$ and $\phi(w)=f$, we see that coffee'' encounterseww'' since $coff=\phi(eww)$. The density of $V$ in $W$ is the proportion of substrings of $W$ that are homomorphic images of $V$. So the density of eww'' incoffee'' is $6/{7 \choose 2}$. A word is \emph{doubled} if every letter that appears in the word appears at least twice.

Recently in the Algebra and Logic Seminar and at the GSCC in Kentucky, I presented the following result: Let $V$ be a word over any alphabet, $\Sigma$ a finite alphabet with at least 2 letters, and $W _ n \in \Sigma^n$ chosen uniformly at random; $V$ is doubled if and only if $\delta(V,W _ n)=0$ asymptotically almost surely.

This talk will focus on the distribution of the density of doubled words and is independent of the previous presentations. Joint work with Josh Cooper.

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