On longest palindromic subwords of finite binary words (Q2037574)

The authors disprove a conjecture on palindromic (scattered) subwords of circular words, stated by \textit{C. Müllner} and \textit{A. Ryzhikov} [Lect. Notes Comput. Sci. 11417, 460--468 (2019; Zbl 1425.68334)]. Namely, they find a series of circular words of the form \(w_1w_2w_3w_4\) of length \(n\) such that the longest palindrome \(p = qq^R\) of an even length such that either \(q\) is a subword of \(w_1 w_2\) and of \((w_3 w_4)^R\) or \(q\) is a subword of \(w_2 w_3\) and of \((w_4 w_1)^R\) is of length less than \(n/2\). The shortest of these examples is of length \(10000\), and the limit of the length of \(qq^R\) is \(15n/32\). They also prove that the maximal length of \(qq^R\) cannot be less than \(3n/8\).