Three-quarter palindromic subsequence conjecture for binary words

Let ww be a binary word of length nn, meaning a word over {0,1}\{0,1\}. Assume that ww has no three consecutive equal letters.

Three-quarter palindrome conjecture. The word ww has a palindromic subsequence of length at least

34(n2).\frac34(n-2).

This strengthens the proved lower bound 23(n2)\frac23(n-2) for both palindromic and antipalindromic subsequences under the same restriction. The conjecture was checked computationally through n=30n=30, with examples based on (001)i(011)i(001)^i(011)^i indicating tightness.

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.