Combinatorics of cyclic shifts in sylvester monoids

Cain, A. J., and A. Malheiro Combinatorics of cyclic shifts in sylvester monoids., Submitted.


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. In the cyclic shift graph of the sylvester monoid (the monoid of binary search trees) of rank n, connected components consist of elements that have the same evaluation (that is, contain the same number of each generating symbol). This paper investigates the diameters of connected components of this graph, and shows that the connected component consisting of elements containing exactly one of each symbol has diameter at least n−1 and at most n.