02/06/2017, 15:00 — 16:00 — Room 6.2.38, Faculty of Sciences of the Universidade de Lisboa
Ricardo Mamede, Universidade de Coimbra
Gray codes for the hyperoctahedral group
A (cyclic) $n$-bit Gray code is a (cyclic) ordering of all $2^n$ binary words of length $n$ such that consecutive words differ in a single bit. Alternatively, an $n$-bit Gray code can be viewed as a Hamiltonian path of the $n$- dimensional hypercube $Q_n$, and a cyclic Gray code as a Hamiltonian cycle of $Q_n$. This idea has been generalized as follows. A Gray code for any combinatorial family of objects is a listing of all objects in that family such that successive objects differ in some prescribed, usually “small", way. The definition of “small" depends on the particular family, its context, and its applications. In this talk, we construct Gray codes for the finite reflection groups, with a particular focus on signed permutations and some of its restrictions: signed involutions and signed involutions without fixed points.
