On the central levels problem

DOI10.1016/J.JCTB.2022.12.008MaRDI QIDQ6330366arXivFDO

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

Publication date 3 December 2019

Published in arXiv

Full work available at URL https://doi.org/10.1016/J.JCTB.2022.12.008

Mathematics Subject Classification ID

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

arXiv classification

cs.DMmath.CO

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.

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)