Publikace na Matematicko-fyzikální fakulta |
2021
Abstrakt
In a recent paper, Mullner and Ryzhikov posed a question about palindromic subwords of finite binary words which can be rephrased as follows: Given four equally long binary words w(1), w(2), w(3), w(4) of total length n, what is the size of a longest palindrome p = qq(R) such that (i) q is a subword of w(1)w(2) and also of (w(3)w(4))(R) or (ii) q is a subword of w(2)w(3) and also of (w(4)w(1))(R)? Milllner and Ryzhikov conjectured that the answer is at least n/2. We disprove this conjecture, constructing sequences of words w(1), w(2), w(3), w(4) such that the longest palindromes have size 15n/32 + o(n).
Additionally, we show that the longest palindromes have size at least 3n/8. (C) 2021 Elsevier B.V. All rights reserved.