Brevier–Preissmann–Sebő strong antipalindromic subsequence conjecture

Let ww be a binary circular word of length nn divisible by 66 with equal numbers of zeros and ones. A circular word can be represented as a concatenation of linear words, and a subsequence is taken in the corresponding linear representation. An antipalindrome is a binary word whose opposite letters are distinct.

Brevier–Preissmann–Sebő's conjecture. The word ww can be partitioned into two linear words w1,w2w_1,w_2 of equal length, w=w1w2w=w_1w_2, having subsequences s1,s2s_1,s_2 such that s1s2s_1s_2 is an antipalindrome and

s1=s2=13w.|s_1|=|s_2|=\frac{1}{3}|w|.

This strengthens the Lyngsø–Pedersen conjecture by requiring the two halves of the antipalindromic subsequence to come from opposite halves of a balanced cut of the circle. It was checked computationally through n=30n=30; the source gives a weaker proved bound with each half of length 14w\frac14|w|.

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.