IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

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.

© Interdisciplinary Mathematics Institute | The University of South Carolina Board of Trustees | Webmaster
USC