Gray codes and symmetric chains

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Gray codes and symmetric chains

Popis výsledku v původním jazyce

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 &lt; l &lt; 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 &gt;= 12. (c) 2021 Elsevier Inc. All rights reserved.

Název v anglickém jazyce

Gray codes and symmetric chains

Popis výsledku anglicky

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 &lt; l &lt; 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 &gt;= 12. (c) 2021 Elsevier Inc. All rights reserved.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GA19-08554S" target="_blank" >GA19-08554S: Struktury a algoritmy ve velmi symetrických grafech</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2022

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Journal of Combinatorial Theory. Series B

ISSN

0095-8956

e-ISSN

1096-0902

Svazek periodika

153

Číslo periodika v rámci svazku

březen

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

30

Strana od-do

31-60

Kód UT WoS článku

000720434900002

EID výsledku v databázi Scopus

2-s2.0-85119088131