Organizers: Brett Stevens (School of Mathematics and Statistics, Carleton University), Joe Buhler (Reed College), Persi Diaconis (Stanford University), Fan Chung (University of California, San Diego), Ronald Graham (University of California, San Diego), Frank Ruskey (University of Victoria).
To our knowledge, no meeting has yet focused on the theory, constructions, and generalizations of de Bruijn cycles, despite the fact that many people in diverse areas have been working on aspects of universal cycles of one kind or another.
Several recent strands of activity suggest that the time is ripe for bringing workers together in this area. The fragments of Donald Knuth's Volume 4a of {\it The Art of Computer Programming} that are available on the web have numerous references to universal cycles of various combinatorial objects, giving applications to the efficient representation, storage, and generation of combinatorial families. Recently, Stevens {\it et al} showed that universal cycles of $n-2$-subsets of an $n$-set do {\it not} exist, despite the fact that (for odd~$n$) the obvious necessary conditions are satisfied. Berlekamp obtained results on universal cycles of subspaces of finite vector spaces, which have been considerably extended by Buhler, Jackson, and Mayer. Stevens described the idea of Beckett-Gray codes, which combine minimal interchange properties from Gray codes and de Bruijn cycles.
The primary goals of this workshop will be to give an overview of the various known results on de Bruijn sequences and universal cycles in general, and to exploit the diversity of the attendees in order to stimulate new work. The workshop is likely to focus on several questions in which progress seems imminent or likely, and we will now enumerate some of these areas.
Universal cycles are a form of Gray codes where the minimal interchange property is that of being successive states of the given information being passed through a fixed length queue data structure. This representation gives very compact representations of data-- twice as good as standard Gray code representations. Beckett-Gray codes, Single Track Gray codes and Gray's own binary reflected code are strong examples. What data structure and Gray code compatibilities are useful? What combinatorial families can be represented compatibly with them?
Linear constructions of classical de Bruijn cycles (i.e., shift-register sequences) have limitations. As mentioned earlier, locating where a given binary $n$-tuple lies is equivalent to the discrete logarithm problem in a finite field. For this reason, nonlinear constructions have been used, and there are constructions that allow both fast location of a string and fast determination of which string begins at position~$j$. One can investigate similar questions for general universal cycles.
The problem of finding universal cycles of subspaces of vector spaces is likely to generate interest, since newer results provide tantalizing hints of very general approaches.
The result of Stevens {\it et al} on $n-2$-subsets of an $n$-set is the first broad non-existence result about universal cycles, and the workshop will examine this result and attempt to push the underlying techniques further.
In summary, vast generalizations of a simple combinatorial idea are beginning to appear in many areas. The workshop aims to bring work in coding theory, number theory, algebra, computer science, and combinatorics together to: (1) attempt an overview of what is known about classical de Bruijn sequences, (2) present what is available and unknown for universal sequences. We hope to bring people with these disparate backgrounds to foster work across fields, leading to new mathematics and, we hope, to the solution of hard open problems. We anticipate publication of workshop proceedings and associated research results.