For a rational number $r$ such that $1<r\leq 2$, an undirected $r$-power is a word of the form $xyx'$, where the word $x$ is nonempty, the word $x'$ is in $\{ x,x^R\}$, and we have $|xyx'|/|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\geq 4$. We conjecture that $\mbox{ URT}(k)=\tfrac{ k-1}{ k-2}$ for all $k\geq 4$, and we confirm this conjecture for $k\in\{ 4,5,\ldots,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.
Categories: math.CO cs.DM cs.FL