Example

$ \def\sa#1{\tt{#1}} $

The words $\sa{abba}$ and $\sa{baab}$ are both palindromes and conjugate of each other. On the contrary, the word $\sa{aabaa}$ has no other conjugate palindrome, that is to say, its conjugacy class contains only one palindrome.

The conjugacy class of $\sa{abba}$, set $\{\sa{abba},\sa{bbaa},\sa{baab},\sa{aabb}\}$, contains only two palindromes. This is also the case for the word $(\sa{abba})^3$ whose conjugacy class contains $\sa{abbaab}\,\sa{baabba}$ and $\sa{baabba}\,\sa{abbaab}$, two palindromes. But the conjugacy class of $(\sa{abba})^2$ has only one palindrome among its four conjugates.

Problem 12: Conjugate Palindromes

The problem is related to the two operations on words consisting of reversing a word and taking one of its conjugate. The operations are essentially incompatible in the sense that only a few conjugates of a word are also its reverse.

To examine the situation, we consider palindromes that are conjugates of each other.

What is the maximal number of palindromes in the conjugacy class of a word?

Consider the primitive root of two conjugate palindromes.

References

C. Guo, J. Shallit, and A. M. Shur. On the combinatorics of palindromes and antipalindromes. CoRR, abs/1503.09112, 2015.

125 Problems in Text Algorithms

Example

Problem 12: Conjugate Palindromes

References