Generalized middle levels conjecture for hypercube level subgraphs

About 10 years old · traced to

Let QnQ_n be the nn-dimensional hypercube, and let Qn,[a,b]Q_{n,[a,b]} denote the subgraph induced by the vertices whose levels lie in [a,b][a,b]. For integers k≥1k\geq 1 and c∈{0,1,…,k}c\in\{0,1,\ldots,k\}, consider Q2k+1,[k−c,k+1+c]Q_{2k+1,[k-c,k+1+c]}. Generalized middle levels conjecture. For any k≥1k\geq 1 and c∈{0,1,…,k}c\in\{0,1,\ldots,k\}, the graph Q2k+1,[k−c,k+1+c]Q_{2k+1,[k-c,k+1+c]} has a Hamilton cycle. The case c=0c=0 is the middle levels conjecture, which was announced as solved recently; the generalized cases were presented as remaining open and are used to reduce the other open instances of the enumeration problem.

References

Primary source

Petr Gregor and Torsten Mütze, “Trimming and gluing Gray codes”, arXiv:1607.08806 (2018).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.