Search

A short proof of the middle-levels theorem, Discrete Analysis 2018:8, 12 pp. Let $n$ be a positive integer, and define a bipartite graph where one vertex set consists of all subsets of $\{1,2,\dots,2n+1\}$ of size $n$, the other consists of all subsets of size $n+1$, and we join a set $A$ of size $n$ to a set $B$ of size $n+1$ if and only if $A\subset B$. The following innocent looking question was an open problem for a long time: does this graph contain a Hamilton cycle? That is, can we find a sequence of sets $A_1,B_1,\dots,A_N,B_N$ (where $N=\binom{2n+1}n$) such that each set of size $n$ or $n+1$ appears exactly once, and such that $A_1$ is contained in $B_1$, which contains $A_2$, which is contained in $B_2$, and so on all the way up to $B_N$, which contains $A_1$? For very small values of $n$, one can find Hamilton cycles, and one can even imagine that one is finding them in a potentially systematic way, but in the end all patterns seem to evaporate. One difficulty is that it can be shown that in any Hamilton cycle, each of the $2n+1$ possible edge directions must occur the same number of times. This means that if one tries to use a solution to the $n-1$ case to build a Hamilton cycle for the $n$ case, one will have to chop it up into exponentially many pieces. (This is in sharp contrast with the case of the entire $n$-dimensional cube, where one can easily prove that it contains a Hamilton cycle by taking two parallel Hamilton cycles in copies of an $(n-1)$-dimensional cube, removing an edge from the first and the corresponding edge from the second, and adding two linking edges to form a single Hamilton cycle.) Another approach that one might imagine attempting to use is a probabilistic one, perhaps creating most of a Hamilton cycle randomly and then making a few adjustments at the end in order to complete it. But this kind of argument also runs into problems: the constraints are not too severe to start with, but the more of the cycle one constructs, the stronger they become, and without a clever idea one gets stuck long before completing a cycle. In 2014 the problem, by then over 30 years old, was solved by Torsten Mütze [1], one of the authors of this paper, using a long and technical (and constructive) argument. This paper gives a much shorter and simpler argument that avoids nearly all the technicalities of the first argument and thereby makes Mütze's remarkable result truly accessible for the first time. Very roughly, the idea behind the proof is to begin by finding a certain special collection $\mathcal C$ of vertex-disjoint cycles that includes all vertices. If there were only one cycle in the collection, we would be done, but since that is not the case, we have to join them together. This is done by using an auxiliary collection of 6-cycles: if a 6-cycle intersects the union of two cycles $C_1,C_2$ in a particular way, then the symmetric difference of all three cycles is a single cycle that visits the same vertices as $C_1$ and $C_2$. The authors prove various lemmas about the cycles in $\mathcal C$ and the 6-cycles, which they then use to prove that this process can be continued until there is just one cycle left. (The reason 6-cycles are used, rather than 4-cycles as in the case of the complete cube, is brutally simple: it is easy to check that the middle-layers graph does not contain any 4-cycles.) The proof gives rise to an efficient algorithm for actually finding Hamilton cycles in the middle-layers graph. If you are curious to see what the cycles look like, the algorithm can be run online on [this web page](http://page.math.tu-berlin.de/~muetze/cos/middle.html). [1] Torsten Mütze, _Proof of the middle levels conjecture_, Proc. London Math. Soc. *112* (2016), pp. 677-713. Also available at [arXiv:1404.4442](https://arxiv.org/abs/1404.4442)

We consider the algorithmic problem of generating each subset of [ n ] : = { 1 , 2 , … , n } whose size is in some interval [ k , l ] , 0 ≤ k ≤ l ≤ n , exactly once (cyclically) by repeatedly adding or removing a single element, or by exchanging a single element. For k = 0 and l = n this is the classical problem of generating all 2 n subsets of [ n ] by element additions/removals, and for k = l this is the classical problem of generating all ( n k ) subsets of [ n ] by element exchanges. We prove the existence of such cyclic minimum-change enumerations for a large range of values n , k , and l , improving upon and generalizing several previous results. For all these existential results we provide optimal algorithms to compute the corresponding Gray codes in constant O ( 1 ) time per generated set and O ( n ) space. Rephrased in terms of graph theory, our results establish the existence of (almost) Hamilton cycles in the subgraph of the n -dimensional cube Q n induced by all levels [ k , l ] . We reduce all remaining open cases to a generalized version of the middle levels conjecture, which asserts that the subgraph of Q 2 k + 1 induced by all levels [ k − c , k + 1 + c ] , c ∈ { 0 , 1 , … , k } , has a Hamilton cycle. We also prove an approximate version of this generalized conjecture, showing that this graph has a cycle that visits a ( 1 − o ( 1 ) ) -fraction of all vertices.

Does every matching in the n-dimensional hypercube Qn extend to a Hamiltonian cycle? This question was raised by Ruskey and Savage in 1993 and even though a positive answer in known in some special cases, the problem still remains open in general. In this paper we present recent results on extendability of matchings in hypercubes to Hamiltonian cycles and paths as well as on the computational complexity of these problems, motivated by the Ruskey-Savage question. Moreover, we verify the conjecture of Vandenbussche and West saying that every matching in Qn, n≥2, extends to a 2-factor.

An $n$-bit Gray code is a sequence of all $n$-bit strings such that consecutive strings differ in a single bit. It is well-known that given $\alpha,\beta\in\{0,1\}^n$, an $n$-bit Gray code between $\alpha$ and $\beta$ exists iff the Hamming distance $d(\alpha,\beta)$ of $\alpha$ and $\beta$ is odd. We generalize this classical result to $k$ pairwise disjoint pairs $\alpha_i, \beta_i\in\{0,1\}^n$: if $d(\alpha_i,\beta_i)$ is odd for all $i$ and $k1$ with one exception in the case when $n = k + 1 = 4$. Our result is optimal in the sense that for every $n>2$ there are $n$ pairwise disjoint pairs $\alpha_i,\beta_i\in\{0,1\}^n$ with $d(\alpha_i,\beta_i)$ odd for which such sequences do not exist., Comment: 30 pages, 2 figures

An incidence in a graph G is a pair (v, e) where v is a vertex of G and e is an edge of G incident to v. Two incidences (v, e) and (u, f) are adjacent if at least one of the following holds: \((a) v = u, (b) e = f\), or \((c) vu \in \{e,f\}\). An incidence coloring of G is a coloring of its incidences assigning distinct colors to adjacent incidences. In this note we prove that every subquartic graph admits an incidence coloring with at most seven colors.

Locke (Am Math Mon 108:668, 2001) conjectured that the n-dimensional hypercube $$Q_n$$Qn with the set F of 2k removed vertices half from each bipartition set, where $$n \ge k + 2$$nźk+2 and $$k \ge 1$$kź1, is Hamiltonian. So far the conjecture remains open although partial results are known; some of them with additional conditions on the set F. We explore Hamiltonian properties of $$Q_n - F$$Qn-F if the set of faulty vertices F forms either an isometric cycle of $$Q_n$$Qn or an isometric tree of $$Q_n$$Qn. We study a more general problem. A bipartite graph G is Hamiltonian laceable if either (a) its bipartition sets are of equal size and for each pair of vertices x, y from different bipartition sets there exists a Hamiltonian path between x and y, or (b) its bipartition sets differ in sizes by one and for each pair of vertices x, y from the larger bipartition set there exists a Hamiltonian path between x and y. In particular, we show that if C is an isometric cycle in $$Q_n$$Qn for $$n \ge 5$$nź5, then $$Q_n - V(C)$$Qn-V(C) is Hamiltonian laceable. This allows us to remove up to 2n faulty vertices. Furthermore, if T is balanced isometric tree in $$Q_n$$Qn, then for $$n \ge 4$$nź4 the graph $$Q_n - V(T)$$Qn-V(T) is Hamiltonian laceable. Finally, if T is an almost-balanced isometric tree in $$Q_n$$Qn, then for $$n \ge 5$$nź5 the graph $$Q_n - V(T)$$Qn-V(T) is Hamiltonian laceable. Thus our results support Locke hypothesis.

A binary (cyclic) Gray code is a (cyclic) ordering of all binary strings of the same length such that any two consecutive strings differ in a single bit. This corresponds to a Hamiltonian path (cycle) in the hypercube. Fink showed that every perfect matching in the $n$-dimensional hypercube $Q_n$ can be extended to a Hamiltonian cycle, confirming a conjecture of Kreweras. In this paper, we study the "path version" of this problem. Namely, we characterize when a perfect matching in $Q_n$ extends to a Hamiltonian path between two prescribed vertices of opposite parity. Furthermore, we characterize when a perfect matching in $Q_n$ with two faulty vertices extends to a Hamiltonian cycle. In both cases we show that for all dimensions $n\ge 5$ the only forbidden configurations are so-called half-layers, which are certain natural obstacles. These results thus extend Kreweras' conjecture with an additional edge, or with two faulty vertices. The proof for the case $n=5$ is computer-assisted.

In interconnection networks one often needs to broadcast multiple messages in parallel from a single source so that the load at each node is minimal. With this motivation we study a new concept of rooted level-disjoint partitions of graphs. In particular, we develop a general construction of level-disjoint partitions for Cartesian products of graphs that is efficient both in the number of level partitions as in the maximal height. As an example, we show that the hypercube Q?n for every dimension n = 3 ? 2 i or n = 4 ? 2 i where i ? 0 has n level-disjoint partitions with the same root and with maximal height 3 n - 2 . Both the number of such partitions and the maximal height are optimal. Moreover, we conjecture that this holds for any n ? 3.

The linear extension diameter of a finite poset P is the diameter of the graph on all linear extensions of P as vertices, two of them being adjacent whenever they differ in a single adjacent transposition. We determine the linear extension diameter of the subposet of the Boolean lattice induced by the 1st and kth levels and describe an explicit construction of all diametral pairs. This partially solves a question of Felsner and Massow. The diametral pairs are obtained from minimal vertex-edge covers of so called dependency graphs, a new concept which may be of independent interest.

Two ordered Hamiltonian paths in the n-dimensional hypercube Q"n are said to be independent if ith vertices of the paths are distinct for every 1=

The augmented cube AQ n is a hypercube Q n with additional edges between vertices that differ in a suffix. We show that AQ n with f arbitrary faulty edges contains a copy of Q n with at most n 2 n − 1 f faulty edges. This allows to transfer properties of Q n with faulty edges to AQ n with (more) faulty edges. In particular, we show that if f ⩽ 3 n − 7 and each vertex of AQ n is incident with at least two non-faulty edges then AQ n contains a hamiltonian cycle consisting only of non-faulty edges.

A distance magic labeling of a graph G is a bijective assignment of labels from {1, 2, …, |V (G)|} to the vertices of G such that the sum of labels on neighbors of u is the same for all vertices u. We show that the n-dimensional hypercube has a distance magic labeling for every n ≡ 2 ( mod 4 ) . It is known that this condition is also necessary. This completes solution of a conjecture posed by Acharya et al. [B. D. Acharya, S. B. Rao, T. Singh and V. Parameswaran, Neighborhood magic graphs, In National Conference on Graph Theory, Combinatorics and Algorithm, 2004].

An n -bit (cyclic) Gray code is a (cyclic) ordering of all n -bit strings such that consecutive strings differ in exactly one bit. We construct an n -bit cyclic Gray code C n whose graph of transitions is isomorphic to an induced subgraph of the d -dimensional hypercube where d = ? lg n ? . This allows to represent C n so that only ? ( log log n ) bits per n -bit string are needed. We provide an explicit description of an algorithm which generates the transition sequence of C n in linear time with respect to the output size.

Given a set H of binary vectors of length n , is there a cyclic listing of H so that every two successive vectors differ in a single coordinate? The problem of the existence of such a listing, which is called a cyclic Gray code of H , is known to be NP -complete in general. The goal of this paper is therefore to specify boundaries between its intractability and polynomial decidability. For that purpose, we consider a restriction when the vectors of H are of a bounded weight. A weight of a vector u ∈ { 0 , 1 } n is the number of 1’s in u . We show that if every vertex of H has weight k or k + 1 , our problem is decidable in polynomial time for k ≤ 1 and NP -complete for k ≥ 2 . Furthermore, if k = 2 and for every i ∈ [ n ] there are at most m vectors of H of weight two having one in the i -th coordinate, then the problem becomes decidable in polynomial time for m ≤ 3 and NP -complete for m ≥ 13 . The following complementary problem is also known to be NP -hard: given an F ⊆ { 0 , 1 } n , which now plays the role of a set of faults to be avoided, is there a cyclic Gray code of { 0 , 1 } n ∖ F ? We show that if every vertex of F has weight at most k , the problem is decidable in polynomial time for k ≤ 2 and NP -hard for k ≥ 5 . It follows that there is a function f ( n ) = Θ ( n 4 ) such that the existence of a cyclic Gray code of { 0 , 1 } n ∖ F for a given set F ⊆ { 0 , 1 } n of size at most f ( n ) is NP -hard. In addition, we study the cases when the Gray code does not have to be cyclic, and moreover, when the first and the last vectors of the code are prescribed. For these two modifications, all NP -hardness and NP -completeness results hold as well.

A queue layout of a graph consists of a linear ordering $\sigma$ of its vertices and a partition of its edges into sets, called queues, such that in each set no two edges are nested with respect to $\sigma$. We show that the $n$-dimensional hypercube $Q_n$ has a layout into $n-\lfloor \log_2 n \rfloor$ queues for all $n\ge 1$. On the other hand, for every $\varepsilon>0$, every queue layout of $Q_n$ has more than $(\frac{1}{2}-\varepsilon) n-O(1/\varepsilon)$ queues and, in particular, more than $(n-2)/3$ queues. This improves previously known upper and lower bounds on the minimal number of queues in a queue layout of $Q_n$. For the lower bound we employ a new technique of out-in representations and contractions which may be of independent interest.

The linear extension diameter of a finite poset P is the diameter of the graph on all linear extensions of P as vertices, two of them being adjacent whenever they differ in exactly one (adjacent) transposition. Recently, Felsner and Massow determined the linear extension diameter of the Boolean lattice B , and they posed a question of determining the linear extension diameter of a subposet of B induced by two levels. We solve the case of the 1st and k th level. The diametral pairs are obtained from minimal vertex covers of so called dependency graphs, a new concept which may be useful also for the general case.

A queue layout of a graph consists of a linear ordering σ of its vertices, and a partition of its edges into sets, called queues, such that in each set no two edges are nested with respect to σ . A queue-number of G is the minimal number of queues in a queue layout of G . We improve previously known upper and lower bounds on the queue-number of the hypercube.

Let f(n) be the maximum integer such that for every set F of at most f(n) vertices of the hypercube Q n , there exists a cycle of length at least 2 n ?2|F| in Q n ?F. Castaneda and Gotchev conjectured that $f(n)=\binom{n}{2}-2$ . We prove this conjecture. We also prove that for every set F of at most (n 2+n?4)/4 vertices of Q n , there exists a path of length at least 2 n ?2|F|?2 in Q n ?F between any two vertices such that each of them has at most 3 neighbors in F. We introduce a new technique of potentials which could be of independent interest.

Let G"n^k be the subgraph of the hypercube Q"n induced by levels between k and n-k, where n>=2k+1 is odd. The well-known middle-level conjecture asserts that G"2"k"+"1^k is Hamiltonian for all k>=1. We study this problem in G"n^k for fixed k. It is known that G"n^0 and G"n^1 are Hamiltonian for all odd n>=3. In this paper we prove that also G"n^2 is Hamiltonian for all odd n>=5, and we conjecture that G"n^k is Hamiltonian for every k>=0 and every odd n>=2k+1.

A fault-free path in the n-dimensional hypercube Q"n with f faulty vertices is said to be long if it has length at least 2^n-2f-2. Similarly, a fault-free cycle in Q"n is long if it has length at least 2^n-2f. If all faulty vertices are from the same bipartite class of Q"n, such length is the best possible. We show that for every set of at most 2n-4 faulty vertices in Q"n and every two fault-free vertices u and v satisfying a simple necessary condition on neighbors of u and v, there exists a long fault-free path between u and v. This number of faulty vertices is tight and improves the previously known results. Furthermore, we show for every set of at most n^2/10+n/2+1 faulty vertices in Q"n where n>=15 that Q"n has a long fault-free cycle. This is a first quadratic bound, which is known to be asymptotically optimal.

A fault-free cycle in the n-dimensional hypercube Q n with f faulty vertices is long if it has length at least 2 n − 2 f . If all faulty vertices are from the same bipartite class of Q n , such length is the best possible. We prove a conjecture of Castaneda and Gotchev [N. Castaneda and I. S. Gotchev. Embedded paths and cycles in faulty hypercubes. J. Comb. Optim., 2009. doi:10.1007/s10878-008-9205-6 .] asserting that f n = ( n 2 ) − 2 where f n for every set of at most f n faulty vertices, there exists a long fault-free cycle in Q n . Furthermore, we present several results on similar problems of long paths and long routings in faulty hypercubes and their complexity.

Based on the extended Hamming code, for n = 2 r we construct a proper edge-coloring of the n-dimensional hypercube Qn with n colors (i.e. 1-factorization) such that every edge has exactly one parallel edge from each color class except its own. Two edges are said to be parallel if they are opposite on a common 4-cycle. We study properties of this coloring and applications for some Turan-type problems.

A path partition of a graph G is a set of vertex-disjoint paths that cover all vertices of G. Given a set P={{a"i,b"i}}"i"="1^m of pairs of distinct vertices of the n-dimensional hypercube Q"n, is there a path partition {P"i}"i"="1^m of Q"n such that a"i and b"i are endvertices of P"i? Caha and Koubek showed that for 6m==3, there is a balanced set P in Q"n such that 2m-e=n, but no path partition with endvertices prescribed by P exists.

Given a set $\pc=\{a_i,b_i\}_{i=1}^m$ of pairs of vertices in a graph $G$, is there a collection of paths $\{P_i\}_{i=1}^m$ such that $P_i$ connects $a_i$ with $b_i$ and $\{V(P_i)\}_{i=1}^m$ partitions $V(G)$? We study this problem for the graph $Q_n-\ff$ obtained from the $n$-dimensional hypercube $Q_n$ by removing a set $\ff$ of faulty vertices. We show that an obvious necessary condition for the existence of such a partition is also sufficient provided $2|\pc|+ 3|\ff|\le n-3$. As a corollary, we obtain a similar characterization for the existence of a hamiltonian cycle and a hamiltonian path of $Q_n-\ff$ provided $|\ff|\le(n-5)/3$. On the other hand, if the size of $\ff$ is not limited, the problems are NP-complete.

Given a set F of faulty edges or faulty vertices in the hypercube Q n and a pair of vertices u , v , is there a hamiltonian cycle or a hamiltonian path between u and v in Q n − F ? We show that in case F consists of edges forming a matching, or of at most ( n − 7 ) / 4 vertices, then simple necessary conditions are also sufficient. On the other hand, if there are no restrictions on F , all these problems are NP-complete. The solution for faulty vertices was obtained as a special case of a more general result on partitioning Q n − F into vertex-disjoint paths with prescribed endvertices. We also consider a complementary problem with a prescribed set of edges.

An incidence in a graph $G$ is a pair $(v,e)$ where $v$ is a vertex of $G$ and $e$ is an edge of $G$ incident to $v$. Two incidences $(v,e)$ and $(u,f)$ are adjacent if at least one of the following holds: $(a)$ $v = u$, $(b)$ $e = f$, or $(c)$ $vu \in \{e,f\}$. An incidence coloring of $G$ is a coloring of its incidences assigning distinct colors to adjacent incidences. It was conjectured that at most $\Delta(G) + 2$ colors are needed for an incidence coloring of any graph $G$. The conjecture is false in general, but the bound holds for many classes of graphs. We introduce some sufficient properties of the two factor graphs of a Cartesian product graph $G$ for which $G$ admits an incidence coloring with at most $\Delta(G) + 2$ colors., Comment: 11 pages, 5 figures

Given a connected graph G and a set F of faulty vertices of G, let G - F be the graph obtained from G by deletion of all vertices of F and edges incident with them. Is there an algorithm, whose running time may be bounded by a polynomial function of |F| and log |V (G)|, which decides whether G-F is still connected? Even though the answer to this question is negative in general, we describe an algorithm which resolves this problem for the n-dimensional hypercube in time O(|F|n3). Furthermore, we sketch a more general algorithm that is efficient for graph classes with good vertex expansion properties.

Graphs and Algorithms, A (cyclic) n-bit Gray code is a (cyclic) ordering of all 2(n) binary strings of length n such that consecutive strings differ in a single bit. Equivalently, 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). In this paper we study (cyclic) Gray codes avoiding a given set of faulty edges that form a matching. Given a matching M and two vertices u, v of Q(n), n >= 4, our main result provides a necessary and sufficient condition, expressed in terms of forbidden configurations for M, for the existence of a Gray code between u and v that avoids M. As a corollary. we obtain a similar characterization for a cyclic Gray code avoiding M. In particular, in the case that M is a perfect matching, Q(n) has a (cyclic) Gray code that avoids M if and only if Q(n) - M is a connected graph. This complements a recent result of Fink, who proved that every perfect matching of Q(n) can be extended to a Hamiltonian cycle. Furthermore, our results imply that the problem of Hamilionicity of Q(n) with faulty edges, which is NP-complete in general, becomes polynomial for up to 2(n-1) edges provided they form a matching.

Given a family $\{u_i,v_i\}_{i=1}^k$ of pairwise distinct vertices of the $n$-dimensional hypercube $Q_n$ such that the distance of $u_i$ and $v_i$ is odd and $k \leq n-1$, there exists a family $\{P_i\}_{i=1}^k$ of paths such that $u_i$ and $v_i$ are the endvertices of $P_i$ and $\{V(P_i)\}_{i=1}^k$ partitions $V(Q_n)$. This holds for any $n \geq 2$ with one exception in the case when $n=k+1=4$. On the other hand, for any $n \geq 3$ there exist $n$ pairs of vertices satisfying the above condition for which such a family of spanning paths does not exist. We suggest further generalization of this result and explore a relationship to the problem of hamiltonicity of hypercubes with faulty vertices.

We show for every k ≥ 1 that the binomial tree of order 3k has a vertex-coloring with 2k+1 colors such that every path contains some color odd number of times. This disproves a conjecture from [1] asserting that for every tree T the minimal number of colors in a such coloring of T is at least the vertex ranking number of T minus one.

Given a set P of at most 2n-4 prescribed edges (n⩾5) and vertices u and v whose mutual distance is odd, the n-dimensional hypercube Qn contains a hamiltonian path between u and v passing through all edges of P iff the subgraph induced by P consists of pairwise vertex-disjoint paths, none of them having u or v as internal vertices or both of them as endvertices. This resolves a problem of Caha and Koubek who showed that for any n⩾3 there exist vertices u,v and 2n-3 edges of Qn not contained in any hamiltonian path between u and v, but still satisfying the condition above. The proof of the main theorem is based on an inductive construction whose basis for n=5 was verified by a computer search. Classical results on hamiltonian edge-fault tolerance of hypercubes are obtained as a corollary.

Fibonacci cube is a subgraph of hypercube induced on vertices without two consecutive 1's. If we remove from Fibonacci cube the vertices with 1 both in the first and the last position, we obtain Lucas cube. We consider the problem of determining the minimum number of vertices in n-dimensional hypercube whose removal leaves no subgraph isomorphic to m-dimensional Fibonacci cube. The exact values for small m are given and several recursive bounds are established using the symmetry property of Lucas cubes and the technique of labeling. The relation to the problem of subcube fault-tolerance in hypercube is also shown.

Given a set F of vertices of a connected graph G, we study the problem of testing the connectivity of G-F in polynomial time with respect to |F| and the maximum degree @D of G. We present two approaches. The first algorithm for this problem runs in O(|F|@D^2@e^-^1log(|F|@D@e^-^1)) time for every graph G with vertex expansion at least @e>0. The other solution, designed for the class of graphs with cycle basis consisting of cycles of length at most l, leads to O(|F|@D^@?^l^/^2^@?log(|F|@D^@?^l^/^2^@?)) running time. We also present an extension of this method to test the biconnectivity of G-F in O(|F|@D^llog(|F|@D^l)) time.

Recently, Fink [J. Fink, Perfect matchings extend to Hamilton cycles in hypercubes, J. Combin. Theory Ser. B 97 (2007) 1074–1076] affirmatively answered Kreweras’ conjecture asserting that every perfect matching of the hypercube extends to a Hamiltonian cycle. We strengthen this result in the following way. Given a partition of the hypercube into subcubes of nonzero dimensions, we show for every perfect matching of the hypercube that it extends on these subcubes to a Hamiltonian cycle if and only if it interconnects them.

An n-bit (cyclic) Gray code is a (cyclic) sequence of all n-bit strings such that consecutive strings differ in a single bit. We describe an algorithm which for every positive integer n constructs an n-bit cyclic Gray code whose graph of transitions is the d-dimensional hypercube Q d if n = 2 d , or a subgraph of Q d if 2 d ? 1 < n < 2 d . This allows to compress sequences that follow this code so that only ${\it \Theta}(\log\log n)$ bits per n-bit string are needed. The algorithm generates the transitional sequence of the code in a constant amortized time per one transition.

We consider the problem of constructing a cyclic listing of all bitstrings of length 2 n + 1 with Hamming weights in the interval [ n + 1 − l , n + l ] , where 1 ≤ l ≤ n + 1 , by flipping a single bit in each step. This is a far-ranging generalization of the well-known middle two levels problem (the case l = 1 ). We provide a solution for the case l = 2 , and we solve a relaxed version of the problem for general values of l , by constructing cycle factors for those instances. The proof of the first result uses the lexical matchings introduced by Kierstead and Trotter, which we generalize to arbitrary consecutive levels of the hypercube . The proof of the second result uses symmetric chain decompositions of the hypercube, a concept known from the theory of posets . We also present several new constructions of such decompositions based on lexical matchings. In particular, we construct four pairwise edge-disjoint symmetric chain decompositions of the n-dimensional hypercube for any n ≥ 12 .