Brevier–Preissmann–Sebő strong antipalindromic subsequence conjecture

About 7 years old · traced to

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∣=13∣w∣.|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 14∣w∣\frac14|w|.

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.