The undirected repetition threshold and undirected pattern avoidance

Abstract

For a rational number $r$ such that $1<r\le 2$, an undirected $r$-power is a word of the form $xy{x}^{\prime }$, where the word $x$ is nonempty, the word $x^{\prime }$ is in $\{x,x^R\}$, and we have $|xy{x}^{\prime }|/|xy|=r$. The undirected repetition threshold for $k$ letters, denoted $\mbox{URT}(k)$, is the infimum of the set of all $r$ such that undirected $r$-powers are avoidable on $k$ letters. We first demonstrate that $\mbox{URT}(3)=\tfrac{7}{4}$. Then we show that $\mbox{URT}(k)\geq \tfrac{k-1}{k-2}$ for all $k\ge 4$. We conjecture that $\mbox{URT}(k)=\tfrac{k-1}{k-2}$ for all $k\ge 4$, and we confirm this conjecture for $k\in \{4,5,\dots ,21\}.$ We then consider related problems in pattern avoidance; in particular, we find the undirected avoidability index of every binary pattern. This is an extended version of a paper presented at WORDS 2019, and it contains new and improved results.

arXiv admin note: substantial text overlap with arXiv:1904.10029