Tutte seminar - Aaron Williams

Gray codes, universal cycles, and the cool-lex order

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 2ⁿ 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

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

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.