Universal cycles: de Bruijn and beyond
Kenny Paterson
Royal Holloway
The period 16 cyclic sequence s of 0's and 1's:
s = 0000100110101111...
has the following nice property: Take a piece of card and cut a window in it that is exactly 4 symbols long. Placing the card over the sequence, the views we get through the window are 4-tuples of binary symbols. Then, in sliding `discretely' along one period of s, we will see every possible view through the window exactly once each. Sequence s, called a span 4 de Bruijn cycle, has the property that every element from the set of binary 4-tuples is represented in s, and s has minimum period. De Bruijn cycles were `discovered' by de Bruijn in 1946, but actually date back at least as far as Flye-Sainte Marie in 1894.
In this talk we'll consider Universal Cycles (Hurlbert, 1990, Chung, Diaconis and Graham, 1992): these are periodic sequences in which the n-tuples of consecutive positions represent in a natural way all the elements of some set X exactly once each in a period. So a span n de Bruijn sequence is a Universal Cycle for the set X of binary n-tuples. Other sets X that have been considered so far include partitions of an integer, k-permutations of an n-set, k-subsets of an n-set and so on. As just one example to whet the appetite, it is easy to check that:
123423142132432143124134...
is a Universal Cycle for 3-permutations of a 4-set. Knuth has computed that there are 384 such sequences.
Given a set X, the main questions that we study are:
1. Does a Universal Cycle for X exist?
2. If so, how many Universal Cycles are there?
3. Is there an efficient algorithm for generating some (or even all)
Universal Cycles for X?
4. Given a description of a Universal Cycle for X and an element x in
X, is there an efficient algorithm for computing the position in the
Cycle of the n-tuple representing x?
In this talk, we'll sketch some of what's known for each of these questions, focussing mostly on the case where X is the set of n-tuples or the set of k-permutations of an n-set.