On the central levels problem

DOI10.1016/J.JCTB.2022.12.008arXiv1912.01566MaRDI QIDQ6330366FDOQ6330366

Torsten Mütze, Ondřej Mička, Petr Gregor

Publication date: 3 December 2019

Abstract: The 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 $2ell$ levels, has a Hamilton cycle for any $mgeq1$ and $1leelllem+1$. This problem was raised independently by Buck and Wiedemann, Savage, by Gregor and v{S}krekovski, and by Shen and Williams, and it is a common generalization of the well-known middle levels problem, namely the case $ell=1$, and classical binary Gray codes, namely the case $ell=m+1$. In this paper we present a general constructive solution of the central levels problem. Our results also imply the existence of optimal cycles through any sequence of $ell$ consecutive levels in the $n$-dimensional hypercube for any $nge1$ and $1leelllen+1$. Moreover, extending an earlier construction by Streib and Trotter, we construct a Hamilton cycle through the $n$-dimensional hypercube, $ngeq2$, 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.

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Factorials, binomial coefficients, combinatorial functions (05A10) Combinatorics of partially ordered sets (06A07)

This page was built for publication: On the central levels problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6330366)