Asymptotic Density of Zimin Words

Abstract

Word $W$ is an instance of word $V$ provided there is a homomorphism $\varphi$ mapping letters to nonempty words so that $\varphi (V)=W$. For example, taking $\varphi$ such that $\varphi (c)=fr$, $\varphi (o)=e$ and $\varphi (l)=zer$, we see that "freezer" is an instance of "cool". Let ${\mathbb{I}}_n(V,[q])$ be the probability that a random length $n$ word on the alphabet $[q]=\{1,2,\cdots q\}$ is an instance of $V$. Having previously shown that ${\lim }_{n\to \infty }{\mathbb{I}}_n(V,[q])$ exists, we now calculate this limit for two Zimin words, $Z_2=aba$ and $Z_3=abacaba$.

arXiv comment25 pages

References in corpus (2)

• Pattern occurrence statistics and applications to the Ramsey theory of unavoidable patterns
• Toward the Combinatorial Limit Theory of Free Words

Cited by in corpus (1)

• On long words avoiding Zimin patterns