On highly palindromic words: the ternary case (Q777417)

The paper considers palindromes which are scattered subwords of a given finite word. A finite word \(w\) over an \(n\)-letter alphabet is called minimal-palindromic if the longest palindrome in it is of length \(\lceil |w|/n \rceil\); clearly, a palindrome of this length always exists as a subword of the prevalent letter. In [Discrete Appl. Math. 157, No. 5, 953--959 (2009; Zbl 1187.68363)], \textit{Š. Holub} and \textit{K. Saari} proved that each binary word can be extended to the left and to the right to a minimal palindromic word, and introduced the MP-ratio of a word \(w\) as the minimal ratio \(|pws|/|w|\), where \(pws\) is such an extension of \(w\). They also proved that for every binary word, the MP-ratio exists and is bounded from above by \(4\). In this paper, the analogous results are obtained for all ternary words: it is proven that the MP-ratio of a ternary word exists, is bounded from above by \(6\), and the bound is the best possible. The results are rather technical and the presentation is dense and complicated.