|
%I #26 Sep 07 2018 00:51:02
%S 1,1,3,3,5,5,6,7,7,8,9,9,11,11,12,13,13,14,15,15,17,17,18,19,19,20,21,
%T 21,22,23,23,24
%N Minimum length of longest palindromic subsequence, where the minimum is taken over all binary circular words of length n.
%C Here "subsequence" means "scattered subsequence" (not necessarily contiguous). A circular word "wraps around".
%C Slide 10 of Andrew Ryzhikov's talk contains the conjecture that a(n) >= 3n/4, but this conjecture fails for n = 2 and n = 62 (at least). The length-62 counterexample 11111111000000000001010001110110000011010011111001000111010111, where the longest palindromic subsequence is of length 45, was found by Antonio Molina Lovett.
%H Andrew Ryzhikov, <a href="https://7b394770-a-62cb3a1a-s-sites.googlegroups.com/site/ryzandrew/slides_Ryzhikov.pdf">Regular subsequences in finite words</a>, talk for the Workshop on Words and Complexity, 19-23 Feb 2018, Villeurbanne, France.
%e Consider the circular word 0001011. A rotation of this circular word gives 0101100, and deleting the first 1 gives the subsequence 001100, which is a palindrome of length 6. This shows that a(7) >= 6.
%K nonn,more
%O 1,3
%A _Jeffrey Shallit_, Sep 05 2018
%E Terms a(19)-a(32) computed by Antonio Molina Lovett
|
