Computationally Speaking Seminar Series: Gray codes: Easier and Harder

Title: Gray codes: Easier and Harder

Abstract: A Gray code is an ordering of all n-bit binary strings in which consecutive strings
differ in a single bit. For example, 00, 01, 11, 10 is the binary reflected Gray code (BRGC) for n
= 2. Dozens of puzzles are designed to have the BRGC as their solution, including Spin-Out
by Binary Arts (n=7), The Brain by Mag-N if (n=8), as well as the venerable Towers of Hanoi
and Baguenaudier (Chinese ring puzzle). While these puzzles are fun, they can also become
tedious as they require an exponential number of moves, and intermediate states have only
one correct move forward and one incorrect move backward. We present a more general
puzzle framework which supports more moves from each state as well as "Grey code"
solutions as short as n2 moves—so long as you know what you are doing.
Our second topic involves computational complexity. Suppose that we are given a subset of
the n-bit binary strings, and we want to know if that subset has a Gray code. In other words,
we want to know if there is a Hamilton path in a particular induced subgraph of the n-cube.
We show that this problem is NP-hard by a reduction from the Grid Graph Hamilton path
problem. Then we use this foundational result to prove that scores of similar problems are
NP-hard. This includes ordering subsets of permutations using adjacent-transpositions, and
spanning trees using edge-pivots. The latter result complements the recent papers Pivot
Gray Codes for the Spanning Trees of a Graph ft. the Fan by Cameron, Grubb, and Sawada

About the Speaker: Aaron Williams is one of the strongest
researchers in the area of combinatorial generation. He is wellknown
for his engaging and innovative presentations. He is an
Associate Professor at Williams College, USA. 3-0