Orthogonal-cut palindromic subsequence conjecture

Let ww be a word of length nn divisible by 44, with a linear representation

w=w1w2w3w4w=w_1w_2w_3w_4

where the four blocks have equal length. Let p1p1p_1p'_1 and p2p2p_2p'_2 be longest palindromic subsequences with p1=p1|p_1|=|p'_1| and p2=p2|p_2|=|p'_2|, where p1,p1,p2,p2p_1,p'_1,p_2,p'_2 are subsequences of w1w2,w3w4,w2w3,w4w1w_1w_2,w_3w_4,w_2w_3,w_4w_1, respectively.

Orthogonal-cut conjecture. For every such ww and every such linear representation, the maximum of the lengths of p1p1p_1p'_1 and p2p2p_2p'_2 is at least

12n.\frac12n.

This tests the strong circular-palindrome problem using two orthogonal cuts rather than all equal-half cuts. The source offers it as a simplification motivated by the difficulty of the stronger conjecture; no resolution is reported.

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.