Tutte seminar - Aaron WilliamsExport this event to calendar

Friday, September 5, 2008 — 3:30 PM to 4:30 PM EDT

Gray codes, universal cycles, and the cool-lex order

Speaker: Aaron Williams
Affiliation: University of Victoria
Room: Mathematics & Computer Building (MC) 5158

Abstract:

The research area of combinatorial generation is concerned with minimal-change orderings for combinatorial objects of a particular type. For example, the binary reflected Gray code orders the binary strings of length n such that each successive string differs from the previous string in exactly one bit. As another example, a de Bruijn cycle is a string of length 2n that contains each binary string of length n exactly once as a substring. Both concepts have had numerous applications since their introduction in the mid-1940s, and are illustrated below for n = 3

000, 001, 011, 010, 110, 111, 101, 100

11101000.

 

This talk introduces the cool-lex variation on lexicographic order. When applied to many well-known combinatorial objects - including combinations, permutations, balanced parentheses, necklaces with fixed-content, and so on - the result is aright-shift Gray code. This means that each successive string differs from the previous string by shifting a single symbol to the right. For example, the permutations of the multiset {1, 2, 2, 3} appear below in cool-lex order

3221, 2213, 2123, 1223, 2231, 2321, 3212, 2132, 1232, 2312, 3122, 1322.

Furthermore, there is a simple rule that determines each successive shift. Another application of cool-lex order is in the construction of shorthand universal cycles, which are a natural generalization of de Bruijn cycles. For example, the following string

322132123122

contains the substrings 322, 221, 213, 132, … which are shorthand for the multiset permutations 3221, 2213, 2132, 1322, … of {1, 2, 2, 3} since the rightmost symbol is redundant and is omitted. Shorthand universal cycles are easy to construct using cool-lex order, and provide their first known construction. 

The results in this talk are from my PhD thesis, which is under the supervision of Frank Ruskey and Wendy Myrvold at the University of Victoria.

Location 
MC - Mathematics & Computer Building
5158
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
29
30
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
  1. 2019 (143)
    1. October (14)
    2. September (15)
    3. August (9)
    4. July (17)
    5. June (18)
    6. May (16)
    7. April (9)
    8. March (24)
    9. February (13)
    10. January (8)
  2. 2018 (138)
    1. December (2)
    2. November (18)
    3. October (14)
    4. September (9)
    5. August (2)
    6. July (10)
    7. June (13)
    8. May (17)
    9. April (9)
    10. March (19)
    11. February (14)
    12. January (11)
  3. 2017 (103)
  4. 2016 (137)
  5. 2015 (136)
  6. 2014 (88)
  7. 2013 (48)
  8. 2012 (39)
  9. 2011 (36)
  10. 2010 (40)
  11. 2009 (40)
  12. 2008 (39)
  13. 2007 (15)