The Library
On the central levels problem
Tools
Tools
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. ISSN 1868-8969. doi:10.4230/LIPIcs.ICALP.2020.60
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 > 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 | |||||||||
| 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
