Universal updates of Dyck-nest signatures
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2022
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866908376635539456 |
|---|---|
| author | Dejter, Italo J. |
| author_facet | Dejter, Italo J. |
| contents | Let $0<k\in\mathbb{Z}$. The anchored Dyck words of length $n=2k+1$ (obtained by prefixing a 0-bit to each Dyck word of length $2k$ and used to reinterpret the Hamilton cycles in the odd graph $O_k$ and the middle-levels graph $M_k$ found by Mütze et al.) represent in $O_k$ (resp., $M_k$) the cycles of an $n$- (resp., $2n$-) 2-factor and its cyclic (resp., dihedral) vertex classes, and are equivalent to Dyck-nest signatures. A sequence is obtained by updating these signatures according to the depth-first order of a tree of restricted growth strings (RGS's), reducing the RGS-generation of Dyck words by collapsing to a single update the time-consuming $i$-nested castling used to reach each non-root Dyck word or Dyck nest. This update is universal, for it does not depend on $k$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2209_11122 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Universal updates of Dyck-nest signatures Dejter, Italo J. Combinatorics 11Y55, 68W32, 05A05, 06A05 (primary), 05C62, 05C75, 05C05, 05C15 (secondary) Let $0<k\in\mathbb{Z}$. The anchored Dyck words of length $n=2k+1$ (obtained by prefixing a 0-bit to each Dyck word of length $2k$ and used to reinterpret the Hamilton cycles in the odd graph $O_k$ and the middle-levels graph $M_k$ found by Mütze et al.) represent in $O_k$ (resp., $M_k$) the cycles of an $n$- (resp., $2n$-) 2-factor and its cyclic (resp., dihedral) vertex classes, and are equivalent to Dyck-nest signatures. A sequence is obtained by updating these signatures according to the depth-first order of a tree of restricted growth strings (RGS's), reducing the RGS-generation of Dyck words by collapsing to a single update the time-consuming $i$-nested castling used to reach each non-root Dyck word or Dyck nest. This update is universal, for it does not depend on $k$. |
| title | Universal updates of Dyck-nest signatures |
| topic | Combinatorics 11Y55, 68W32, 05A05, 06A05 (primary), 05C62, 05C75, 05C05, 05C15 (secondary) |
| url | https://arxiv.org/abs/2209.11122 |