Gray codes and symmetric chains
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F22%3A10450675" target="_blank" >RIV/00216208:11320/22:10450675 - isvavai.cz</a>
Result on the web
<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=z8DP~Q91FK" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=z8DP~Q91FK</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1016/j.jctb.2021.10.008" target="_blank" >10.1016/j.jctb.2021.10.008</a>
Alternative languages
Result language
angličtina
Original language name
Gray codes and symmetric chains
Original language description
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 (the case l = 1). We provide a solution for the case l = 2, and we solve a relaxed version of the problem for general values of $, by constructing cycle factors for those instances. The proof of the first result uses the lexical matchings introduced by Kierstead and Trotter, which we generalize to arbitrary consecutive levels of the hypercube. The proof of the second result uses symmetric chain decompositions of the hypercube, a concept known from the theory of posets. We also present several new constructions of such decompositions based on lexical matchings. In particular, we construct four pairwise edge disjoint symmetric chain decompositions of the n-dimensional hypercube for any n >= 12. (c) 2021 Elsevier Inc. All rights reserved.
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
<a href="/en/project/GA19-08554S" target="_blank" >GA19-08554S: Structures and algorithms in highly symmetric graphs</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2022
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Journal of Combinatorial Theory. Series B
ISSN
0095-8956
e-ISSN
1096-0902
Volume of the periodical
153
Issue of the periodical within the volume
březen
Country of publishing house
US - UNITED STATES
Number of pages
30
Pages from-to
31-60
UT code for WoS article
000720434900002
EID of the result in the Scopus database
2-s2.0-85119088131