Department of
Applied
Mathematics

Trimming and gluing Gray codes

Torsten Mütze

Abstract

(joint work with Petr Gregor)

We consider the algorithmic problem of generating each subset of [n]:={1,2,...,n} whose size is in some interval [a,b], 0<=a<=b<=n, exactly once (cyclically) by repeatedly adding or removing a single element, or by exchanging a single element. For a=0 and b=n this is the classical problem of generating all 2^n subsets of [n] by element additions/removals, and for a=b this is the classical problem of generating all \binom{n}{a} subsets of [n] by element exchanges. In graph theoretical terms, we ask for the existence of (almost) Hamilton cycles in the subgraph of the n-dimensional cube Q_n induced by all levels [a,b]. We prove the existence of such cycles for a large range of values n, a, and b, and provide corresponding optimal generation algorithms, improving upon and generalizing several previous results.