The undirected repetition threshold and undirected pattern avoidance
read the original abstract
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.
This paper has not been read by Pith yet.
Forward citations
Cited by 1 Pith paper
-
Efficient Analytic Uncertainty Quantification for Multi-Modal Regression
Extends VBI to QR and CR for analytic ELBO and predictive densities in multi-modal regression, outperforming baselines and enabling active learning.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.