2026-08-17T19:53:28Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12467 2024-03-06T10:50:13Z ddc:004 open_access

On the Central Levels Problem Gregor, Petr Mička, Ondřej Mütze, Torsten Gray code Hamilton cycle hypercube middle levels symmetric chain decomposition The central levels problem asserts that the subgraph of the (2m+1)-dimensional hypercube induced by all bitstrings with at least m+1-𝓁 many 1s and at most m+𝓁 many 1s, i.e., the vertices in the middle 2𝓁 levels, has a Hamilton cycle for any m ≥ 1 and 1 ≤ 𝓁 ≤ m+1. This problem was raised independently by Savage, by Gregor and Škrekovski, and by Shen and Williams, and it is a common generalization of the well-known middle levels problem, namely the case 𝓁 = 1, and classical binary Gray codes, namely the case 𝓁 = 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 𝓁 consecutive levels in the n-dimensional hypercube for any n ≥ 1 and 1 ≤ 𝓁 ≤ 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Petr Gregor and Ondřej Mička and Torsten Mütze 2020 Is Part Of LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2020.60 urn:nbn:de:0030-drops-124678 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.60 eng https://creativecommons.org/licenses/by/3.0/legalcode