Crystal monoids and crystal bases: rewriting systems and biautomatic structures for Plactic monoids

Robert Gray (East Anglia)

Frank Adams 1,

The Plactic monoid is a fundamental algebraic object which captures a natural monoid structure carried by the set of semistandard Young tableaux. It arose originally in the work of Schensted (1961) on algorithms for finding the maximal length of a nondecreasing subsequence of a given word over the ordered alphabet A_n = {1 < 2 < . . . < n}. The output of Schensted’s algorithm is a tableau and, by identifying pairs of words that lead to the same tableau, one obtains the Plactic monoid Pl(A_n) of rank n. Alternatively, the Plactic monoid may be defined by a finite presentation with generating symbols A_n and a certain finite set of defining relations which were originally determined in work of Knuth (1970). A third way of obtaining this monoid comes from Kashiwara’s theory of crystal bases. The vertices of any Kashiwara crystal graph carry a natural monoid structure given by identifying words labelling vertices that appear in the same position of isomorphic components of the crystal. In the special case of Kashiwara crystals of type A_n the monoid that arises from this construction turns out to be the Plactic monoid Pl(A_n). In this talk I will explain these three different ways of looking at the Plactic monoid, and how they lead to the general notion of a crystal monoid. Then I will present some recent joint work with A. J. Cain and A. Malheiro investigating these monoids. In particular I will discuss the problem of constructing complete rewriting systems, and finding biautomatic structures, for crystal monoids.

Import this event to your Outlook calendar
▲ Up to the top