Example

The words and are both palindromes and conjugate of each other. On the contrary, the word has no other conjugate palindrome, that is to say, its conjugacy class contains only one palindrome.

The conjugacy class of , set , contains only two palindromes. This is also the case for the word whose conjugacy class contains and , two palindromes. But the conjugacy class of 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