##### Department of Mathematics,

University of California San Diego

****************************

### Math 269 - Combinatorics

## Aaron Williams

#### Department of Mathematics and Statistics, McGill University

## Gray Codes and Universal Cycles: Thinking Locally instead of Globally

##### Abstract:

The term "Gray code" usually refers to an ordering of the n-bit binary strings in which successive strings differ in a single bit. For example, 000, 001, 011, 010, 110, 111, 101, 100 suffices for $n=3$. The term "de Bruijn sequence" usually refers to a circular string of $2^n$ bits in which each n-bit binary string appears once as a substring. For example, 0000100110101111 suffices for $n=4$ since its substrings are 0000, 0001, 0010, ..., 1110, 1100, 1000 (where the last three substrings wrap-around). These concepts have natural generalizations to other combinatorial objects. For example, 123, 132, 312, 321, 231, 213 is a Gray code for the permutations of {1,2,3} in which successive permutations differ by an adjacent-transposition. Simiarly, 321312 is a universal cycle for the 2-permutations of {1,2,3}. (The term "universal cycle" is often used for non-binary de Bruijn sequences.) Gray codes and universal cycles are usually constructed 'globally', meaning that the overall order is easy to describe. In this talk, we instead consider 'local' constructions, where it is easy to describe the next object in the order. With this change in focus, we are able to unify a number of previous results, and solve several well-known open problems. The talk will begin with an overview of the research area and its applications, and should be of interest to computer scientists and discrete mathematicians.

Host: Jeff Remmel

### September 30, 2013

### 4:00 PM

### AP&M 6402

****************************