Combinatorics of cyclic shifts in plactic, hypoplactic, sylvester, Baxter, and related monoids
The cyclic shift graph of a monoid is the graph whose vertices are elements of the monoid and whose edges link elements that differ by a cyclic shift. This paper examines the cyclic shift graphs of `plactic-like' monoids, whose elements can be viewed as combinatorial objects of some type: aside...
Main Authors: | , |
---|---|
Format: | Report |
Language: | unknown |
Published: |
arXiv
2017
|
Subjects: | |
Online Access: | https://dx.doi.org/10.48550/arxiv.1709.03974 https://arxiv.org/abs/1709.03974 |
id |
ftdatacite:10.48550/arxiv.1709.03974 |
---|---|
record_format |
openpolar |
spelling |
ftdatacite:10.48550/arxiv.1709.03974 2023-05-15T18:30:36+02:00 Combinatorics of cyclic shifts in plactic, hypoplactic, sylvester, Baxter, and related monoids Cain, Alan J. Malheiro, António 2017 https://dx.doi.org/10.48550/arxiv.1709.03974 https://arxiv.org/abs/1709.03974 unknown arXiv arXiv.org perpetual, non-exclusive license http://arxiv.org/licenses/nonexclusive-distrib/1.0/ Combinatorics math.CO Group Theory math.GR FOS Mathematics 05E99 Primary, 05C12, 20M05 Secondary Preprint Article article CreativeWork 2017 ftdatacite https://doi.org/10.48550/arxiv.1709.03974 2022-04-01T10:14:22Z The cyclic shift graph of a monoid is the graph whose vertices are elements of the monoid and whose edges link elements that differ by a cyclic shift. This paper examines the cyclic shift graphs of `plactic-like' monoids, whose elements can be viewed as combinatorial objects of some type: aside from the plactic monoid itself (the monoid of Young tableaux), examples include the hypoplactic monoid (quasi-ribbon tableaux), the sylvester monoid (binary search trees), the stalactic monoid (stalactic tableaux), the taiga monoid (binary search trees with multiplicities), and the Baxter monoid (pairs of twin binary search trees). It was already known that for many of these monoids, connected components of the cyclic shift graph consist of elements that have the same evaluation (that is, contain the same number of each generating symbol). This paper focusses on the maximum diameter of a connected component of the cyclic shift graph of these monoids in the rank-$n$ case. For the hypoplactic monoid, this is $n-1$; for the sylvester and taiga monoids, at least $n-1$ and at most $n$; for the stalactic monoid, $3$ (except for ranks $1$ and $2$, when it is respectively $0$ and $1$); for the plactic monoid, at least $n-1$ and at most $2n-3$. The current state of knowledge, including new and previously-known results, is summarized in a table. : 61 pages. Complete proofs of results previously announced in arXiv:1611.04152 Report taiga DataCite Metadata Store (German National Library of Science and Technology) Baxter ENVELOPE(162.533,162.533,-74.367,-74.367) |
institution |
Open Polar |
collection |
DataCite Metadata Store (German National Library of Science and Technology) |
op_collection_id |
ftdatacite |
language |
unknown |
topic |
Combinatorics math.CO Group Theory math.GR FOS Mathematics 05E99 Primary, 05C12, 20M05 Secondary |
spellingShingle |
Combinatorics math.CO Group Theory math.GR FOS Mathematics 05E99 Primary, 05C12, 20M05 Secondary Cain, Alan J. Malheiro, António Combinatorics of cyclic shifts in plactic, hypoplactic, sylvester, Baxter, and related monoids |
topic_facet |
Combinatorics math.CO Group Theory math.GR FOS Mathematics 05E99 Primary, 05C12, 20M05 Secondary |
description |
The cyclic shift graph of a monoid is the graph whose vertices are elements of the monoid and whose edges link elements that differ by a cyclic shift. This paper examines the cyclic shift graphs of `plactic-like' monoids, whose elements can be viewed as combinatorial objects of some type: aside from the plactic monoid itself (the monoid of Young tableaux), examples include the hypoplactic monoid (quasi-ribbon tableaux), the sylvester monoid (binary search trees), the stalactic monoid (stalactic tableaux), the taiga monoid (binary search trees with multiplicities), and the Baxter monoid (pairs of twin binary search trees). It was already known that for many of these monoids, connected components of the cyclic shift graph consist of elements that have the same evaluation (that is, contain the same number of each generating symbol). This paper focusses on the maximum diameter of a connected component of the cyclic shift graph of these monoids in the rank-$n$ case. For the hypoplactic monoid, this is $n-1$; for the sylvester and taiga monoids, at least $n-1$ and at most $n$; for the stalactic monoid, $3$ (except for ranks $1$ and $2$, when it is respectively $0$ and $1$); for the plactic monoid, at least $n-1$ and at most $2n-3$. The current state of knowledge, including new and previously-known results, is summarized in a table. : 61 pages. Complete proofs of results previously announced in arXiv:1611.04152 |
format |
Report |
author |
Cain, Alan J. Malheiro, António |
author_facet |
Cain, Alan J. Malheiro, António |
author_sort |
Cain, Alan J. |
title |
Combinatorics of cyclic shifts in plactic, hypoplactic, sylvester, Baxter, and related monoids |
title_short |
Combinatorics of cyclic shifts in plactic, hypoplactic, sylvester, Baxter, and related monoids |
title_full |
Combinatorics of cyclic shifts in plactic, hypoplactic, sylvester, Baxter, and related monoids |
title_fullStr |
Combinatorics of cyclic shifts in plactic, hypoplactic, sylvester, Baxter, and related monoids |
title_full_unstemmed |
Combinatorics of cyclic shifts in plactic, hypoplactic, sylvester, Baxter, and related monoids |
title_sort |
combinatorics of cyclic shifts in plactic, hypoplactic, sylvester, baxter, and related monoids |
publisher |
arXiv |
publishDate |
2017 |
url |
https://dx.doi.org/10.48550/arxiv.1709.03974 https://arxiv.org/abs/1709.03974 |
long_lat |
ENVELOPE(162.533,162.533,-74.367,-74.367) |
geographic |
Baxter |
geographic_facet |
Baxter |
genre |
taiga |
genre_facet |
taiga |
op_rights |
arXiv.org perpetual, non-exclusive license http://arxiv.org/licenses/nonexclusive-distrib/1.0/ |
op_doi |
https://doi.org/10.48550/arxiv.1709.03974 |
_version_ |
1766214128212377600 |