The Library
On the central levels problem
Tools
Gregor, Petr, Micka, Ondrej and Mutze, Torsten (2023) On the central levels problem. Journal of Combinatorial Theory Series B, 160 . pp. 163-205. doi:10.1016/j.jctb.2022.12.008 ISSN 0095-8956.
|
PDF
WRAP-On-the-central-levels-problem-Mutze-2023.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (1151Kb) | Preview |
Official URL: https://doi.org/10.1016/j.jctb.2022.12.008
Abstract
The central levels problem asserts that the subgraph of the (2m+1)-dimensional hypercube induced by all bitstrings with at least m+1-l many 1s and at most m+l many 1s, i.e., the vertices in the middle 2l levels, has a Hamilton cycle for any m>=1 and 1=<l=<m+1. This problem was raised independently by Buck and Wiedemann, Savage, Gregor and Skrekovski, and by Shen and Williams, and it is a common generalization of the well-known middle levels problem, namely the case l=1, and classical binary Gray codes, namely the case l=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 l consecutive levels in the n-dimensional hypercube for any n>=1 and 1=<l=<n+1. Moreover, extending an earlier construction by Streib and Trotter, we construct a Hamilton cycle through the n-dimensional hypercube, n>=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.
Item Type: | Journal Article | |||||||||
---|---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software |
|||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | |||||||||
Library of Congress Subject Headings (LCSH): | Gray codes , Hamiltonian systems, Hypercube | |||||||||
Journal or Publication Title: | Journal of Combinatorial Theory Series B | |||||||||
Publisher: | Elsevier | |||||||||
ISSN: | 0095-8956 | |||||||||
Official Date: | May 2023 | |||||||||
Dates: |
|
|||||||||
Volume: | 160 | |||||||||
Page Range: | pp. 163-205 | |||||||||
DOI: | 10.1016/j.jctb.2022.12.008 | |||||||||
Status: | Peer Reviewed | |||||||||
Publication Status: | Published | |||||||||
Access rights to Published version: | Open Access (Creative Commons) | |||||||||
Date of first compliant deposit: | 23 January 2023 | |||||||||
Date of first compliant Open Access: | 23 January 2023 | |||||||||
RIOXX Funder/Project Grant: |
|
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year