The undirected repetition threshold

Abstract

For rational $1<r\le 2$, an undirected $r$-power is a word of the form $xy{x}^{\prime }$, where $x$ is nonempty, $x^{\prime }\in \{x,x^{\mathrm{R}}\}$, and $|xy{x}^{\prime }|/|xy|=r$. The undirected repetition threshold for $k$ letters, denoted $\mathrm{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 $\mathrm{URT}(3)=\frac{7}{4}$. Then we show that $\mathrm{URT}(k)\ge \frac{k-1}{k-2}$ for all $k\ge 4$. We conjecture that $\mathrm{URT}(k)=\frac{k-1}{k-2}$ for all $k\ge 4$, and we confirm this conjecture for $k\in \{4,8,12\}.$

16 pages. Accepted to the WORDS 2019 conference. This version includes minor changes suggested by the anonymous referees