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.
DIMACS Home Page