ICE-TCS Talk - Amy Glen - Palindromic Richness

In 2001, Droubay, Justin, and Pirillo showed that any finite word w of length |w| contains at most |w| + 1 distinct palindromes (including the empty word). Inspired by this result, Jacques Justin and I recently initiated a unified study of finite and infinite words that are characterized by containing the maximal number of distinct palindromes, which we call "rich words" (in view of their palindromic richness). In this talk I will explore various properties of this intriguing class of words. In particular, I will show that a nice characteristic property of rich words is that all "complete returns" to any palindromic factor are palindromes. These words encompass the well-known family of episturmian words, originally introduced by Droubay et al. in 2001. Another special class of rich words consists of sequences with "abundant palindromic prefixes", which were introduced and studied by Fischler in 2006 in relation to Diophantine approximation. Other examples of rich words have appeared in many different contexts; they include complementation-symmetric Rote sequences, symbolic codings of trajectories of symmetric interval exchange transformations, trapezoidal words, and a certain class of words associated with $\beta$-expansions where $\beta$ is a simple Parry number. I will finish by presenting more recent results on rich words (particularly characterizations) obtained in collaboration with Michelangelo Bucci, Alessandro De Luca, Aldo de Luca, Steve Widmer, and Luca Q. Zamboni.