Strong palindromic subsequence conjecture for binary circular words

About 7 years old · traced to

Let ww be a binary circular word of length nn divisible by 66. Choose a linear representation and partition it as w=w1w2w=w_1w_2 into two linear words of equal length. Let s1s_1 and s2s_2 be subsequences of w1w_1 and w2w_2, respectively, and let s2Rs_2^R denote reversal.

Strong circular-palindrome conjecture. There is such a partition with subsequences s1,s2s_1,s_2 satisfying

s1=s2Rs_1=s_2^R

—that is, s1s2s_1s_2 is a palindrome—and

∣s1s2∣=23∣w∣.|s_1s_2|=\frac{2}{3}|w|.

This strengthens the weak circular-palindrome conjecture by aligning the two halves of the palindrome with a cut into equal halves of the circle. The source notes that the bound 12n\frac12n is proved, while no stronger bound is known.

References

Primary source

Clemens Müllner and Andrew Ryzhikov, “Palindromic Subsequences in Finite Words”, arXiv:1901.07502 (2019).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.