Strong palindromic subsequence conjecture for binary circular words

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=23w.|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.

Sources & referencesView supporting material

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.