The Library
On the central levels problem
Tools
Gregor, Petr, Micka, Ondrej and Mutze, Torsten (2020) On the central levels problem. In: 47th International Colloquium on Automata, Languages, and Programming, Saarbrücken, 8-11 Jul 2020. Published in: 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), 168 60:1-60:17. ISBN 9783959771382. doi:10.4230/LIPIcs.ICALP.2020.60 ISSN 1868-8969.
This is the latest version of this item.
|
PDF
WRAP-On-the-central-levels-problem-Mutzer-2020.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution. Download (853Kb) | Preview |
Official URL: https://doi.org/10.4230/LIPIcs.ICALP.2020.60
Abstract
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$.
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$.
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 $n\ge 1$ and $1\le \ell \le n+1$.
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.
Item Type: | Conference Item (Paper) | |||||||||
---|---|---|---|---|---|---|---|---|---|---|
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 , Combinatorial analysis, Hypercube, Computer science -- Mathematics | |||||||||
Series Name: | LIPIcs–Leibniz International Proceedings in Informatics | |||||||||
Journal or Publication Title: | 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020) | |||||||||
Publisher: | LIPIcs | |||||||||
ISBN: | 9783959771382 | |||||||||
ISSN: | 1868-8969 | |||||||||
Official Date: | June 2020 | |||||||||
Dates: |
|
|||||||||
Volume: | 168 | |||||||||
Page Range: | 60:1-60:17 | |||||||||
DOI: | 10.4230/LIPIcs.ICALP.2020.60 | |||||||||
Status: | Peer Reviewed | |||||||||
Publication Status: | Published | |||||||||
Access rights to Published version: | Restricted or Subscription Access | |||||||||
Date of first compliant deposit: | 5 October 2020 | |||||||||
Date of first compliant Open Access: | 12 October 2020 | |||||||||
RIOXX Funder/Project Grant: |
|
|||||||||
Conference Paper Type: | Paper | |||||||||
Title of Event: | 47th International Colloquium on Automata, Languages, and Programming | |||||||||
Type of Event: | Conference | |||||||||
Location of Event: | Saarbrücken | |||||||||
Date(s) of Event: | 8-11 Jul 2020 | |||||||||
Related URLs: | ||||||||||
Open Access Version: |
Request changes or add full text files to a record
Available Versions of this Item
- On the central levels problem. (deposited 12 Oct 2020 14:30) [Currently Displayed]
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year