The undirected repetition threshold and undirected pattern avoidance (Q2662683)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The undirected repetition threshold and undirected pattern avoidance |
scientific article |
Statements
The undirected repetition threshold and undirected pattern avoidance (English)
0 references
14 April 2021
0 references
An (ordinary) \(r\)-power (a.k.a. gapped repeat) is a word of the form \(xyx\), where \(x\) is a nonempty word, and \(|xyx|/|xy| = r\). This generalizes the classical notions of squares, cubes, etc. to fractional exponents. The repetition threshold \(\operatorname{RT}(k)\) is the infimum of rational numbers \(r\) such that \(r\)-powers are avoidable for infinite words over an alphabet of \(k\) letters. It has been conjectured by F.~Dejean and then proved, with the effort of many researchers, that \(\operatorname{RT}(3)=7/4\), \(\operatorname{RT}(4)=7/5\) and \(\operatorname{RT}(k)=k/(k-1)\) for all \(k \geq 5\). In this paper, the authors generalize this line of research to \emph{undirected \(r\)-powers}, which they define as words of the form \(xyx'\), where \(x\) is a nonempty word, \(x'\in\{x,x^R\}\) and \(|xyx'|/|xy| = r\), where \(x^R\) denotes the reversal of \(x\). The undirected repetition threshold \(\operatorname{URT}(k)\) is defined accordingly. Clearly, \(\operatorname{RT}(k)\leq \operatorname{URT}(k)\) for all \(k\geq 2\), since an \(r\)-power is a particular case of an undirected \(r\)-power. The authors prove that \(\operatorname{URT}(3) = 7/4\) and that \(\operatorname{URT}(k) \geq (k-1)/(k-2)\) for every \(k \geq 4\), and conjecture that actually \(\operatorname{URT}(k) = (k-1)/(k-2)\) for every \(k \geq 4\). They prove the conjecture for all \(k\in\{4,\ldots,21\}\).
0 references
repetition thresholds
0 references
gapped repeats
0 references
gapped palindromes
0 references
pattern avoidance
0 references
patterns with reversal
0 references
0 references