2016/11/13 by Alan J. Cain, Cain, Alan J., António Malheiro +1
Computer Science · Mathematics · #05C12 #05E99 (Primary) #20M05 (Secondary) #Advanced Topics in Algebra #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Group Theory (math.GR) #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1611.04152
openalex publication_date 2016/11/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The cyclic shift graph of a monoid is the graph whose vertices are elements\nof the monoid and whose edges link elements that differ by a cyclic shift. For\ncertain monoids connected with combinatorics, such as the plactic monoid (the\nmonoid of Young tableaux) and the sylvester monoid (the monoid of binary search\ntrees), connected components consist of elements that have the same evaluation\n(that is, contain the same number of each generating symbol). This paper\ndiscusses new results on the diameters of connected components of the cyclic\nshift graphs of the finite-rank analogues of these monoids, showing that the\nmaximum diameter of a connected component is dependent only on the rank. The\nproof techniques are explained in the case of the sylvester monoid.\n