DIMACS TR: 93-05

Monotone Gray Codes and the Middle Levels Problem



Authors: Carla D. Savage and Peter Winkler

ABSTRACT

An n-bit binary Gray code is an enumeration of all n-bit binary strings so that successive elements differ in exactly one bit position; equivalently, a hamilton path in the Hasse diagram of B_n (the partially ordered set of subsets of an n-element set, ordered by inclusion.) We construct, for each n, a hamilton path in B_n with the following additional property: edges between levels i-1 and i of B_n must appear on the path before edges between levels i and i+1. Two consequences are an embedding of the hypercube into a linear array which simultaneously minimizes dilation in both directions, and a long path in the middle two levels of B_n.

Using a second recursive construction, we are able to improve still further on this path, thus obtaining the best known results on the notorious "middle levels" problem (to show that the graph formed by the middle two levels of B_2k+1 is hamiltonian for all k). We show in fact that for every epsilon > 0, there is an h >= 1 so that if a hamilton cycle exists in the middle two levels of B_2k+1 for 1 >= k <= h, then there is a cycle of length at least (1-epsilon)N(k) for ALL k >= 1, where N(k) = 2(k+1 choose k). Using the fact that hamilton cycles are currently known to exist for 1 <= k <= 11, the construction guarantees a cycle of length at least .839 N(k) in the middle two levels of B_2k+1 for all k.

Paper available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-05.ps

DIMACS Home Page