Gray codes, universal cycles, and the cool-lex order
Speaker: | Aaron Williams |
---|---|
Affiliation: | University of Victoria |
Room: | Mathematics & Computer Building (MC) 5158 |
Abstract:
The research area of combinatorial generation is concerned with minimal-change orderings for combinatorial objects of a particular type. For example, the binary reflected Gray code orders the binary strings of length n such that each successive string differs from the previous string in exactly one bit. As another example, a de Bruijn cycle is a string of length 2n that contains each binary string of length n exactly once as a substring. Both concepts have had numerous applications since their introduction in the mid-1940s, and are illustrated below for n = 3
000, 001, 011, 010, 110, 111, 101, 100
11101000.
This talk introduces the cool-lex variation on lexicographic order. When applied to many well-known combinatorial objects - including combinations, permutations, balanced parentheses, necklaces with fixed-content, and so on - the result is aright-shift Gray code. This means that each successive string differs from the previous string by shifting a single symbol to the right. For example, the permutations of the multiset {1, 2, 2, 3} appear below in cool-lex order
3221, 2213, 2123, 1223, 2231, 2321, 3212, 2132, 1232, 2312, 3122, 1322. |
Furthermore, there is a simple rule that determines each successive shift. Another application of cool-lex order is in the construction of shorthand universal cycles, which are a natural generalization of de Bruijn cycles. For example, the following string
contains
the
substrings
322,
221,
213,
132,
…
which
are shorthand
for
the
multiset
permutations
3221,
2213,
2132,
1322,
…
of
{1,
2,
2,
3}
since
the
rightmost
symbol
is
redundant
and
is
omitted.
Shorthand
universal
cycles
are
easy
to
construct
using
cool-lex
order,
and
provide
their
first
known
construction.
The
results
in
this
talk
are
from
my
PhD
thesis,
which
is
under
the
supervision
of
Frank
Ruskey
and
Wendy
Myrvold
at
the
University
of
Victoria.