On the central levels problem

Autor: Petr Gregor, Ondřej Mička, Torsten Mütze
Rok vydání: 2023
Předmět:
Zdroj: Journal of Combinatorial Theory, Series B. 160:163-205
ISSN: 0095-8956
1868-8969
DOI: 10.1016/j.jctb.2022.12.008
Popis: The \emph{central levels problem} asserts that the subgraph of the $(2m+1)$-dimensional hypercube induced by all bitstrings with at least $m+1-\ell$ many 1s and at most $m+\ell$ many 1s, i.e., the vertices in the middle $2\ell$ levels, has a Hamilton cycle for any $m\geq 1$ and $1\le \ell\le m+1$.\ud This problem was raised independently by Buck and Wiedemann, Savage, Gregor and {\v{S}}krekovski, and by Shen and Williams, and it is a common generalization of the well-known \emph{middle levels problem}, namely the case $\ell=1$, and classical binary Gray codes, namely the case $\ell=m+1$.\ud In this paper we present a general constructive solution of the central levels problem.\ud Our results also imply the existence of optimal cycles through any sequence of $\ell$ consecutive levels in the $n$-dimensional hypercube for any $n\ge 1$ and $1\le \ell \le n+1$.\ud Moreover, extending an earlier construction by Streib and Trotter, we construct a Hamilton cycle through the $n$-dimensional hypercube, $n\geq 2$, that contains the symmetric chain decomposition constructed by Greene and Kleitman in the 1970s, and we provide a loopless algorithm for computing the corresponding Gray code.
Databáze: OpenAIRE
Externí odkaz: