# Analogues of the Knuth and Forgotten equivalences on permutations: have they been studied?

Consider a totally ordered alphabet $A$ of $n$ letters. Let $W$ be the set of all words over $A$ which have no two letters equal. Then, for example, we can define the Knuth equivalence on $W$ as the smallest equivalence relation $\equiv$ which satisfies the following two properties:

• If a word $w$ is obtained from another word $w^{\prime}$ by finding in $w^{\prime}$ a subword of the form $bca$ with $a < b < c$ and replacing it by $bac$, then $w \equiv w^{\prime}$.

• If a word $w$ is obtained from another word $w^{\prime}$ by finding in $w^{\prime}$ a subword of the form $acb$ with $a < b < c$ and replacing it by $cab$, then $w \equiv w^{\prime}$.

In short, we say that the Knuth equivalence is "the equivalence relation generated by $bca\equiv bac$ and $acb\equiv cab$".

The Knuth equivalence has been studied a lot (suitably extended to words with possibly equal letters, it gives rise to the so-called plactic monoid and has a significant role in the modern theory of the symmetric group and Young tableaux).

A similar relation, namely the one generated by $acb\equiv bac$ and $bca\equiv cab$, has been studied by Novelli and Schilling in arXiv:0706.2996v3 and been called the "forgotten equivalence".

William Kuszmaul, a student I am mentoring in the MIT Primes project, has been working on systematically analyzing equivalence relations like this (continuing the work started in Linton, Propp, Roby, West, arXiv:1111.3920 and Pierrot, Rossin, West, FPSAC 2011), and was able to, e. g., compute the number of equivalence classes for many of them.

What we would like to know is how many such equivalence relations have already been studied. We are particularly interested in those of the form "equivalence relation generated by $...\equiv ...$ and $...\equiv ...$", since both the Knuth and the forgotten equivalence are of that type (as opposed to, say, the Chinese one), and it is these relations that, for some reason, turn out in algebraic contexts (symmetric functions, in particular).

We are interested in three-letter relations only, for the time being; so the hypoplactic monoid is not what we care about.

-
Wow you are 23 and already mentoring students!? –  John Jiang May 6 '12 at 3:55
That's the Primes project ( web.mit.edu/primes ). Most of the mentors are graduate students. –  darij grinberg May 6 '12 at 4:06
Some of the results of my students are on the web now: web.mit.edu/primes/materials/2012/Kuszmaul.pdf (warning: currently obsolete) and web.mit.edu/primes/materials/2012/Kuszmaul-Zhou.pdf (probably not the newest version either). –  darij grinberg Feb 25 '13 at 21:24

The sylvester monoid (with the "s" of "sylvester" in lowercase) is a very good example of a plactic-like monoid. It was introduced by Novelli, Hivert, and Thibon (see The Algebra of Binary Search Trees). It is defined in the following way: Let $(A, \leq)$ be a totally ordered alphabet and consider the monoid congruence $\equiv$ generated by $$ac-b \equiv ca-b$$ for any $a, b, c \in A$ such that $a \leq b < c$ (here, the symbol $-$ denotes an arbitrary factor). Then, the sylvester monoid is $A^*/_\equiv$.

Since $\equiv$-equivalence classes of words the have same commutative image, we can consider $\equiv$-equivalence classes of permutations. Equivalence classes of permutations of $\mathfrak{S}_n$ are in bijection with standard binary search trees (that are binary trees with $n$ internal nodes bijectively labeled on $[n]$).

The analog of the Robinson-Schensted insertion in the context of the sylvester monoid is simply the usual algorithm of insertion of a word (from right to left) in a binary search tree. Furthermore, this monoid is the main ingredient of a very interesting construction of ${\bf PBT}$, a Hopf algebra involving binary search trees which provides a generalization of symmetric functions.

There are a lot of other interesting plactic-like monoids like the Bell monoid (see Algebraic constructions on set partitions). It is the quotient of the free monoid generated by $A$ by the monoid congruence $\equiv$ generated by $$ac \; u \; b \equiv ca \; u \; b,$$ where $a, b, c \in A$, $u \in A^*$, $a \leq b < c$, and any letter $d$ of $u$ satisfies $d \geq c$. Maybe this particular definition can give you some ideas to define new interesting monoids.

Besides, the Baxter monoid (see Algebraic and combinatorial structures on pairs of twin binary trees and The Hopf algebra of diagonal rectangulations) is another plactic-like monoid which involves four letters instead of three.

-
Yes, thank you; this isn't what I was searching for but it's a very beautiful theory (I happen to have read some parts of the Novelli-Hivert-Thibon paper). The Bell monoid is new to me, but I don't see a downloadable file at that link? –  darij grinberg Feb 25 '13 at 21:23
I just have edited the link for the paper dealing with the bell monoid and give the definition of this monoid. –  Samuele Giraudo Feb 26 '13 at 8:18