2026-07-20T11:27:54Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9070 2024-03-06T10:43:17Z ddc:004 open_access

Gray Codes and Symmetric Chains Gregor, Petr Jäger, Sven Mütze, Torsten Sawada, Joe Wille, Kaja Gray code Hamilton cycle hypercube poset symmetric chain We consider the problem of constructing a cyclic listing of all bitstrings of length 2n+1 with Hamming weights in the interval [n+1-l,n+l], where 1 <= l <= n+1, by flipping a single bit in each step. This is a far-ranging generalization of the well-known middle two levels problem (l=1). We provide a solution for the case l=2 and solve a relaxed version of the problem for general values of l, by constructing cycle factors for those instances. Our proof uses symmetric chain decompositions of the hypercube, a concept known from the theory of posets, and we present several new constructions of such decompositions. In particular, we construct four pairwise edge-disjoint symmetric chain decompositions of the n-dimensional hypercube for any n >= 12. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Petr Gregor and Sven Jäger and Torsten Mütze and Joe Sawada and Kaja Wille 2018 Is Part Of LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2018.66 urn:nbn:de:0030-drops-90703 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.66 eng https://creativecommons.org/licenses/by/3.0/legalcode