## Generalized De Bruijn Cycles

- Sept. 28, 2015
- 3:30 p.m.
- LeConte 312

## Abstract

For a set of integers I, we define a q-ary I-cycle to be a assignment of the symbols 1 through q to the integers modulo q^n so that every word appears on some translate of I. This definition generalizes that of de Bruijn cycles, and opens up a multitude of questions. We address the existence of such cycles, discuss “reduced” cycles (ones in which the all-zeroes string need not appear), and provide general bounds on the shortest sequence which contains all words on some translate of I. We also prove a variant on results concerning decompositions of complete graphs into cycles and employ it to resolve the case of |I| = 2 completely. Joint work with Ron Graham.