TY - JOUR

T1 - Combinatorics of cyclic shifts in plactic, hypoplactic, sylvester, Baxter, and related monoids

AU - Cain, Alan J.

AU - Malheiro, António

PY - 2019/10/1

Y1 - 2019/10/1

N2 - 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 focuses 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.

AB - 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 focuses 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.

KW - Binary search tree

KW - Conjugacy

KW - Cyclage

KW - Cyclic shift

KW - Hypoplactic monoid

KW - Plactic monoid

KW - Quasi-ribbon tableau

KW - Sylvester monoid

UR - http://www.scopus.com/inward/record.url?scp=85068467706&partnerID=8YFLogxK

U2 - 10.1016/j.jalgebra.2019.06.025

DO - 10.1016/j.jalgebra.2019.06.025

M3 - Article

AN - SCOPUS:85068467706

SN - 0021-8693

VL - 535

SP - 159

EP - 224

JO - Journal of Algebra

JF - Journal of Algebra

ER -