Title: Generalized de Bruijn words for primitive words and powers
| Speaker: | Gary Au |
| Affiliation: | Milwaukee School of Engineering |
| Room: | MC 5501 |
Abstract:
In
this
talk,
we
will
discuss
some
problems
in
combinatorics
on
words
that
are
related
to
de
Bruijn
words.
We
show
that
for
every
$n
\geq
1$
and
over
any
finite
alphabet,
there
is
a
word
whose
circular
subwords
of
length
$n$
have
a
one-to-one
correspondence
with
the
set
of
primitive
(aperiodic)
words
of
length
$n$,
and
provide
several
ways
to
generate
such
a
word.
We
also
look
into
connections
between
de
Bruijn
graphs
of
primitive
words
and
Lyndon
graphs.
We
also
show
that
the
shortest
word
that
contains
every
$p$-power
of
length
$pn$
over
a
$k$-letter
alphabet
has
length
between
$pk^n$
and
roughly
$(p+
\frac{1}{k})
k^n$,
for
all
integers
$p
\geq
1$,
and
sketch
an
algorithm
that
generates
a
word
which
achieves
the
upper
bound.
This
talk
does
not
assume
any
prior
knowledge
in
combinatorics
on
words,
and
should
be
accessible
to
grad
students
in
all
areas
of
C&O.
(Joint work with Jeffrey Shallit.)