Monotone Gray codes and the middle levels problem (Q1805053)

An \(n\)-bit Gray code is a hamiltonian path in the \(n\)-hypercube \(\mathbb{Z}_2^n\). Define the weight of a vertex as the number of 1's occurring as its coordinates. An \(n\)-bit Gray code is called monotone if all edges between vertices of weight \(i\) and \(i+1\) precede those between vertices of weight \(j\) and \(j+1\), for all \(i<j\). The main result of this paper is the construction of a monotone \(n\)-bit Gray code for all positive integers \(n\). The proof uses induction on \(n\), but is quite explicit. Let \(G_n (i)\) denote the subgraph of the \(n\)-hypercube induced by vertices of weight \(i\) or \(i+1\); it is not known in general whether \(G_n (i)\) has a hamiltonian path. For \(n=2i+1\) this is known as the middle-level problem. This is a special case of the Lovász conjecture, stating that each vertex-transitive graph has a hamiltonian path. Monotone Gray codes give rise to some long cycles in \(G_n (i)\). Two further problems on hamiltonian paths are proposed here.