比利时vs摩洛哥足彩
,
university of california san diego
****************************
math 269 - combinatorics
aaron williams
比利时vs摩洛哥足彩 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
****************************