Abstract
| A \textit{Lyndon word} is a primitive word on an ordered alphabet that is
lexicographically less than all of its conjugates. Originally introduced in the
context of free Lie algebras (Lyndon 1954, Chen-Fox-Lyndon 1958), Lyndon words
have proved to be a useful tool for many problems in combinatorics, such as the
construction of \textit{de Bruijn sequences} (Fredricksen-Maiorana 1978) and
determining the optimal lower bound for the size of uniform unavoidable sets
(Champarnaud \textit{et al.} 2004). A famous theorem concerning Lyndon words
asserts that every finite word can be uniquely factorised as a non-increasing
product of Lyndon words (Chen-Fox-Lyndon 1958). In this sense, Lyndon words are
to combinatorics on words like prime numbers are to number theory.
\medskip
\hspace*{1em} The minimum number of distinct Lyndon factors that a word of
length $n$ can contain is clearly $1$, achieved by $x^n$ where $x$ is a letter.
More interesting are the Lyndon words that contain the minimum number of
distinct Lyndon factors, a subclass of which consists of the so-called
\textit{Fibonacci Lyndon words} (i.e., Lyndon factors of the well-known
\textit{infinite Fibonacci word}). Such words will be the focus of this talk. |