Register for: WIMSIG2017

Details of talk

TitleOn Lyndon words containing the minimum number of Lyndon factors
PresenterAmy Glen (Murdoch University)
Author(s)Amy Glen
SessionAlgebra and Discrete Mathematics
Time14:00:00 2017-09-26

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. 

\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.

Back To Timetable