CRYSTALLIZING THE HYPOPLACTIC MONOID:
FROM QUASI-KASHIWARA OPERATORS TO THE
ROBINSON–SCHENSTED–KNUTH-TYPE
CORRESPONDENCE FOR QUASI-RIBBON TABLEAUX

arXiv:1601.06390v2 [math.CO] 8 Sep 2016

ALAN J. CAIN AND ANTÓNIO MALHEIRO
Abstract. Crystal graphs, in the sense of Kashiwara, 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 particular case of the crystal graph for
the q-analogue of the special linear Lie algebra sln , this monoid
is the celebrated plactic monoid, whose elements can be identified with Young tableaux. The crystal graph and the so-called
Kashiwara operators interact beautifully with the combinatorics
of Young tableaux and with the Robinson–Schensted–Knuth correspondence and so provide powerful combinatorial tools to work
with them. This paper constructs an analogous ‘quasi-crystal’
structure for the hypoplactic monoid, whose elements can be identified with quasi-ribbon tableaux and whose connection with the
theory of quasi-symmetric functions echoes the connection of the
plactic monoid with the theory of symmetric functions. This quasicrystal structure and the associated quasi-Kashiwara operators are
shown to interact just as neatly with the combinatorics of quasiribbon tableaux and with the hypoplactic version of the Robinson–
Schensted–Knuth correspondence. A study is then made of the interaction of the crystal graph of the plactic monoid and the quasicrystal graph for the hypoplactic monoid. Finally, the quasi-crystal
structure is applied to prove some new results about the hypoplactic monoid.

Contents
1. Introduction
2. Preliminaries and notation
2.1. Alphabets and words

2
6
6

2010 Mathematics Subject Classification. Primary 05E15; Secondary 05E05,
20M05.
Key words and phrases. hypoplactic, quasi-ribbon tableau, Robinson–
Schensted–Knuth correspondence, Kashiwara operator, crystal graph.
The first author was supported by an Investigador FCT fellowship
(IF/01622/2013/CP1161/CT0001).
For both authors, this work was partially supported by the Fundação para a
Ciência e a Tecnologia (Portuguese Foundation for Science and Technology) through
the project UID/MAT/00297/2013 (Centro de Matemática e Aplicações).
1

2

ALAN J. CAIN AND ANTÓNIO MALHEIRO

2.2. Compositions and partitions
2.3. Weight
3. Crystals and the plactic monoid
3.1. Young tableaux and insertion
3.2. Kashiwara operators and the crystal graph
3.3. Computing the Kashiwara operators
3.4. Properties of the crystal graph
4. Quasi-ribbon tableaux and insertion
5. Quasi-Kashiwara operators and the quasi-crystal graph
6. The quasi-crystal graph and the hypoplactic monoid
7. The quasi-crystal graph and the Robinson–Schensted–Knuth
correspondence
8. Structure of the quasi-crystal graph
8.1. Sizes of classes and quasi-crystals
8.2. Interaction of the crystal and quasi-crystal graphs
8.3. The Schützenberger involution
8.4. Characterizing quasi-crystal graphs?
9. Applications
9.1. Counting factorizations
9.2. Conjugacy
9.3. Satisfying an identity
References

7
8
8
8
12
14
15
16
20
27
33
34
34
40
49
50
50
50
51
51
52

1. Introduction
A crystal basis, in the sense of Kashiwara [Kas91, Kas90], is (informally) a basis for a representation of a suitable algebra on which
the generators have a particularly neat action. It gives rise, via tensor products, to the crystal graph, which carries a natural monoid
structure given by identifying words labelling vertices that appear in
the same position of isomorphic components. The ubiquitous plactic monoid, whose elements can be viewed as semistandard Young
tableaux, and which appears in such diverse contexts as symmetric
functions [Mac95], representation theory and algebraic combinatorics
[Ful97, Lot02], Kostka–Foulkes polynomials [LS81, LS78], Schubert
polynomials [LS85, LS90], and musical theory [Jed11], arises in this
way from the crystal basis for the q-analogue of the special linear Lie
algebra sln . The crystal graph and the associated Kashiwara operators interact beautifully with the combinatorics of Young tableaux and
with the Robinson–Schensted–Knuth correspondence and so provide
powerful combinatorial tools to work with them.
This paper is dedicated to constructing an analogue of this crystal
structure for the monoid of quasi-ribbon tableaux: the so-called hypoplactic monoid. To explain this aim in more detail, and in particular

CRYSTALLIZING THE HYPOPLACTIC MONOID

3

to describe the properties such an analogue should enjoy, it is necessary to briefly recapitulate some of the theory of crystals and of Young
tableaux.
The plactic monoid of rank n (where n ∈ N) arises by factoring the
free monoid A∗n over the ordered alphabet An = {1 < . . . < n} by a
relation ≡plac , which can be defined in various ways. Using Schensted’s
algorithm [Sch61], which was originally intended to find longest increasing and decreasing subsequences of a given sequence, one can compute
a (semistandard) Young tableau P(w) from a word w ∈ A∗n and so
define ≡plac as relating those words that yield the same Young tableau.
Knuth made a study of correspondences between Young tableaux and
non-negative integer matrices and gave defining relations for the plactic monoid [Knu70]; the relation ≡plac can be viewed as the congruence
generated by these defining relations.
Lascoux & Schützenberger [LS81] began the systematic study of the
plactic monoid, and, as remarked above, connections have emerged
with myriad areas of mathematics, which is one of the reasons Schützenberger proclaimed it ‘one of the most fundamental monoids in algebra’
[Sch97]. Of particular interest for us is how it arises from the crystal
basis for the q-analogue of the special linear Lie algebra sln (that is, the
type An+1 simple Lie algebra), which links it to Kashiwara’s theory of
crystal bases [KN94]. Isomorphisms between connected components of
the crystal graph correspond to the relation ≡plac . Viewed on a purely
combinatorial level, the Kashiwara operators and crystal graph are important tools for working with the plactic monoid. (Indeed, in this
context they are sometimes called ‘coplactic’ operators [Lot02, ch. 5],
being in a sense ‘orthogonal’ to ≡plac .) Similarly, crystal theory can
also be used to analyse the analogous ‘plactic monoids’ that index representations of the q-analogues of symplectic Lie algebras spn (the type
Cn simple Lie algebra), special orthogonal Lie algebras of odd and even
rank so2n+1 and so2n (the type Bn and Dn simple Lie algebras), and
the exceptional simple Lie algebra G2 (see [KS04, Lec02, Lec03] and
the survey [Lec07]). The present authors and Gray applied this crystal
theory to construct finite complete rewriting systems and biautomatic
structures for all these plactic monoids [CGM]; Hage independently
constructed a finite complete rewriting system for the plactic monoid
of type Cn [Hag15].
As is described in detail later in the paper, the crystal structure
meshes neatly with the Robinson–Schensted–Knuth correspondence.
This correspondence is a bijection w ↔ (P, Q) where w is a word over
An , and P is a semistandard Young tableau with entries in An and Q is
a standard Young tableau of the same shape. (The semistandard Young
tableau P is the tableau P(w) computed by Schensted’s algorithm; the
standard tableau Q can be computed in parallel.) Essentially, the
standard Young tableau Q corresponds to the connected component

4

ALAN J. CAIN AND ANTÓNIO MALHEIRO

of the crystal graph in which the word w lies, and the semistandard
Young tableau P corresponds to the position of w in that component.
By holding Q fixed and varying P over semistandard tableaux of the
same shape, one obtains all words in a given connected component.
Consequently, all words in a given connected component correspond to
tableaux of the same shape.
In summary, there are three equivalent approaches to the plactic
monoid:
P1. Generators and relations: the plactic monoid is defined by the
presentation An Rplac , where

Rplac = (acb, cab) : a ≤ b < c

∪ (bac, bca) : a < b ≤ c .

Equivalently, ≡plac is the congruence on A∗n generated by Rplac .
P2. Tableaux and insertion: the relation ≡plac is defined by u ≡plac v
if and only if P(u) = P(v), where P(·) is the Young tableau
computed using the Schensted insertion algorithm (see Algorithm 3.2 below).
P3. Crystals: the relation ≡plac is defined by u ≡plac v if and only if
there is a crystal isomorphism between connected components
of the crystal graph that maps u onto v.

The defining relations in Rplac (known as the Knuth relations) are
the reverse of the ones given in [CGM]. This is because, in the context of crystal bases, the convention for tensor products gives rise to
a ‘plactic monoid’ that is actually anti-isomorphic to the usual notion
of plactic monoid. Since this paper is mainly concerned with combinatorics, rather than representation theory, it follows Shimozono [Shi05]
in using the convention that is compatible with the usual notions of
Young tableaux and the Robinson–Schensted–Knuth correspondence.
Another important aspect of the plactic monoid is its connection to
the theory of symmetric polynomials. The Schur polynomials with n
indeterminates, which are the irreducible polynomial characters of the
general linear group GLn (C), are indexed by shapes of Young tableaux
with entries in An , and they form a Z-basis for the ring of symmetric polynomials in n indeterminates. The plactic monoid was applied
to give the first rigorous proof of the Littlewood–Richardson rule (see
[LR34] and [Gre07, Appendix]), which is a combinatorial rule for expressing a product of two Schur polynomials as a linear combination
of Schur polynomials.
In recent years, there has emerged a substantial theory of noncommutative symmetric functions and quasi-symmetric functions; see,
for example, [GKL+ 95, KT97, KT99]. Of particular interest for this
paper is the notion of quasi-ribbon polynomials, which form a basis for
the ring of quasi-symmetric polynomials, just as the Schur polynomials

CRYSTALLIZING THE HYPOPLACTIC MONOID

5

form a basis for the ring of symmetric polynomials. The quasi-ribbon
polynomials are indexed by the so-called quasi-ribbon tableaux. These
quasi-ribbon tableaux have an insertion algorithm and an associated
monoid called the hypoplactic monoid, which was first studied in depth
by Novelli [Nov00]. The hypoplactic monoid of rank n arises by factoring the free monoid A∗n by a relation ≡hypo , which, like ≡plac , can be
defined in various ways. Using the insertion algorithm one can compute a quasi-ribbon tableau from a word and so define ≡hypo as relating
those words that yield the same quasi-ribbon tableau. Alternatively,
the relation ≡hypo can be viewed as the congruence generated by certain
defining relations.
Thus there are two equivalent approaches to the hypoplactic monoid:
H1. Generators and relations: the hypoplactic monoid is defined by
the presentation An Rhypo , where
Rhypo = Rplac

∪ (cadb, acbd) : a ≤ b < c ≤ d

∪ (bdac, dbca) : a < b ≤ c < d .

Equivalently, ≡hypo is the congruence on the free monoid A∗n
generated by Rhypo .
H2. Tableaux and insertion: the relation ≡hypo is defined by u ≡hypo
v if and only if QR(u) = QR(v), where QR(·) is the quasi-ribbon
tableau computed using the Krob–Thibon insertion algorithm
(see Algorithm 4.3 below).
Krob & Thibon [KT97] proved the equivalence of H1 and H2, which are
the direct analogues of P1 and P2. Owing to the previous success in
detaching crystal basis theory from its representation-theoretic foundation and using it as a combinatorial tool for working with Young
tableaux and plactic monoids, it seems worthwhile to try to find an
analogue of P3 for the hypoplactic monoid. Such an analogue should
have the following form:
H3. Quasi-crystals: the relation ≡hypo is defined by u ≡hypo v if and
only if there is a quasi-crystal isomorphism between connected
components of the quasi-crystal graph that maps u onto v.
The aim of this paper is to define quasi-Kashiwara operators on a
purely combinatorial level, and so construct a quasi-crystal graph as
required for H3. As will be shown, the interaction of the combinatorics
of quasi-ribbon tableaux with this quasi-crystal graph will be a close
analogue of the interaction of the combinatorics of Young tableaux with
the crystal graph (and is, in the authors’ view, just as elegant).
In fact, a related notion of ‘quasi-crystal’ is found in Krob & Thibon [KT99]; see also [Hiv00]. However, the Krob–Thibon quasi-crystal
describes the restriction to quasi-ribbon tableaux (or more precisely
words corresponding to quasi-ribbon tableaux) of the action of the

6

ALAN J. CAIN AND ANTÓNIO MALHEIRO

usual Kashiwara operators: it does not apply to all words and so does
not give rise to isomorphisms that can be used to define the relation
≡hypo .
The paper is organized as follows: Section 2 sets up notation and discusses some preliminaries relating to words, partitions, compositions,
and the notion of weight. Section 3 reviews, without proof, the basic
theory of Young tableaux, the plactic monoid, Kashiwara operators,
and the crystal graph; the aim is to gather the elegant properties of
the crystal structure for the plactic monoid that should be mirrored
in the quasi-crystal structure for the hypoplactic monoid. These properties will also be used in the study of the interactions of the crystal
and quasi-crystal graphs. Section 4 recalls the definitions of quasiribbon tableaux and the hypoplactic monoid. Section 5 states the definition of the quasi-Kashiwara operators and the quasi-crystal graph,
and shows that isomorphisms between connected components of this
quasi-crystal graph give rise to a congruence on the free monoid. Section 6 proves that the corresponding factor monoid is the hypoplactic
monoid. En route, some of the properties of the quasi-crystal graph
are established. Section 7 studies how the quasi-crystal graph interacts with the hypoplactic version of the Robinson–Schensted–Knuth
correspondence. Section 8 systematically studies the structure of the
quasi-crystal graph. It turns out to be a subgraph of the crystal graph
for the plactic monoid, and the interplay of the subgraph and graph
has some very neat properties. Finally, the quasi-crystal structure is
applied to prove some new results about the hypoplactic monoid in
Section 9, including an analogy of the hook-length formula.
2. Preliminaries and notation
2.1. Alphabets and words. Recall that for any alphabet X, the free
monoid (that is, the set of all words, including the empty word) on
the alphabet X is denoted X ∗ . The empty word is denoted ε. For
any u ∈ X ∗ , the length of u is denoted |u|, and, for any x ∈ X,
the number of times the symbol x appears in u is denoted |u|x . Suppose u = u1 · · · uk ∈ X ∗ (where uh ∈ X). For any i ≤ j, the word
ui · · · uj is a factor of u. For any i1 , . . . , im ∈ {1, . . . , k} such that
i1 < i2 < . . . < im , the word ui1 ui2 · · · uim is a subsequence of u. Note
that factors must be made up of consecutive letters, whereas subsequences may be made up of non-consecutive letters. [To minimize
potential confusion, the term ‘subword’ is not used in this paper, since
it tends to be synonymous with ‘factor’ in semigroup theory, but with
‘subsequence’ in combinatorics on words.]
For further background on the free monoid, see [How95]; for presentations, see [Hig92, Ruš95].
Throughout this paper, A will be the set of natural numbers viewed
as an infinite ordered alphabet: A = {1 < 2 < 3 < . . .}. Further, n

CRYSTALLIZING THE HYPOPLACTIC MONOID

7

will be a natural number and An will be the set of the first n natural
numbers viewed as an ordered alphabet: An = {1 < 2 < . . . < n}.
A word u ∈ A∗ is standard if it contains each symbol in {1, . . . , |u|}
exactly once. Let u = u1 · · · uk be a standard word. The word u is
identified with the permutation h 7→ uh , and u−1 denotes the inverse
of this permutation (which is also identifed with a standard word).

Further, the descent set of the standard word u is D(u) = h ∈
{1, . . . , |u| − 1} : uh > uh+1 .
Let u ∈ A∗ . The standardization of u, denoted std(u), is the standard word obtained by the following process: read u from left to right
and, for each a ∈ A, attach a subscript h to the h-th appearance of a.
Symbols with attached subscripts are ordered by

ai < bj ⇐⇒ (a < b) ∨ (a = b) ∧ (i < j) .

Replace each symbol with an attached subscript in u with the corresponding symbol of the same rank from A. The resulting word is
std(u). For example:
w=2 4 3 2 4 5 5 6 5
21 41 31 22 42 51 52 61 53
std(w) = 1 4 3 2 5 6 7 9 8
For further background relating to standard words and standardizaton,
see [Nov00, § 2].
2.2. Compositions and partitions. A weak composition α is a finite
sequence (α1 , . . . , αm ) with terms in N ∪ {0}. The terms αh up to the
last non-zero term are the parts of α. The length of α, denoted `(α),
is the number of its parts. The weight of α, denoted |α|, is the sum
of its parts (or, equivalently, of its terms): |α| = α1 + · · · + αm . For
example, if α = (3, 0, 4, 1, 0), then `(α) = 4 and |α| = 8. Identify weak
compositions whose parts are the same (that is, that differ only in a
tail of terms 0). For example, (3, 1, 5, 2) is identified with (3, 1, 5, 2, 0)
and (3, 1, 5, 2, 0, 0, 0). (Note that this identification does not create
ambiguity in the notions of parts and weight.) A composition is a
weak composition whose parts are all in N. For a composition α =
(α1 , . . . , α`(α) ), define D(α) = {α1 , α1 + α2 , . . . , α1 + . . . + α`(α−)1 }. For
a standard word u ∈ A∗ , define DC(u) to be the unique composition
of weight |u| such that D(DC(u)) = D(u), where D(u) is as defined in
Subsection 2.1. For example, if u = 143256798, then D(u) = {2, 3, 8}
and so DC(u) = (2, 1, 5, 1).
A partition λ is a non-increasing finite sequence (λ1 , . . . , λm ) with
terms in N. The terms λh are the parts of λ. The length of λ, denoted
`(λ), is the number of its parts. The weight of λ, denoted |λ|, is the
sum of its parts: |λ| = λ1 + · · · + λm . For example, if λ = (5, 3, 2, 2),
then `(λ) = 4 and |λ| = 12.

8

ALAN J. CAIN AND ANTÓNIO MALHEIRO

2.3. Weight. The weight function wt is, informally, the function that
counts the number of times each symbol appears in a word. More
formally, wt is defined by

wt : A∗ → (N ∪ {0})A
u 7→ |u|1 , |u|2 , |u|3 , . . . .

Clearly, wt(·) has an infinite tail of components 0, so only the prefix
up to the last non-zero term is considered; thus wt(·) is a weak composition. For example, wt(542164325224) = (1, 4, 1, 3, 2, 1). See [Shi05,
§ 2.1] for a discussion of the basic properties of weight functions.
Weights are compared using the following order:
(2.1)

(α1 , α2 , . . .) ≤ (β1 , β2 , . . .)
k
k
X

X
⇐⇒ (∀k ∈ N)
αi ≤
βi .
i=1

i=1

When |α| = |β|, this is the dominance order of partitions [Sta05, § 7.2].
When wt(u) < wt(v), one says that v has higher weight than u (and u
has lower weight than v). For example,
wt(542164325224) = (1, 4, 1, 3, 2, 1)
< (5, 3, 2, 2, 0, 0) = wt(432143212111);
that is, 432143212111 has higher weight than 542164325224. For the
purposes of this paper, it will generally not be necessary to compare
weights using (2.1); the important fact will be how the Kashiwara
operators affect weight.
3. Crystals and the plactic monoid
This section recalls in detail the three approaches to the plactic
monoid discussed in the introduction, and discusses further the very
elegant interaction of the crystal structure with the combinatorics of
Young tableaux and in particular with the Robinson–Schensted–Knuth
correspondence. The aim is to lay out the various properties one would
hope for in the quasi-crystal structure for the hypoplactic monoid.
3.1. Young tableaux and insertion. The Young diagram of shape
λ, where λ is a partition, is a grid of boxes, with λh boxes in the hth row, for h = 1, . . . , `(λ), with rows left-aligned. For example, the
Young diagram of shape (5, 3, 2, 2) is

A Young diagram of shape (1, 1, . . . , 1) is said to be a column diagram
or to have column shape. Note that, in this paper, Young diagrams are

CRYSTALLIZING THE HYPOPLACTIC MONOID

9

top-left aligned, with longer rows at the top and the parts of the partition specifying row lengths from top to bottom. There is an alternative
convention of bottom-left aligned Young diagrams, where longer rows
are at the bottom.
A Young tableau is a Young diagram that is filled with symbols from
A so that the entries in each row are non-decreasing from left to right,
and the entries in each column are increasing from top to bottom. For
example, a Young tableau of shape (5, 3, 2, 2) is

(3.1)

1
2
4
5

2 2 2 4
3 5
4
6

A Young tableau of shape (1, 1, . . . , 1) is a column. (That is, a column
is a Young tableau of column shape.)
A standard Young tableau of shape λ is a Young diagram that is filled
with symbols from {1, . . . , |λ|}, with each symbol appearing exactly
once, so that the entries in each row are increasing from left to right,
and the entries in each column are increasing from top to bottom. For
example, a standard Young tableau of shape (5, 3, 2, 2) is
1
2
5
8

3 6 7 10
4 12
9
11

A tabloid is an array formed by concatenating columns, filled with
symbols from A so that the entries in each column are increasing from
top to bottom. (Notice that there is no restriction on the relative
heights of the columns; nor is there a condition on the order of entries
in a row.) An example of a tabloid is

(3.2)

2 1 4 1 2
5 3
2
4
4
6
5

Note that a tableau is a special kind of tabloid. The shape of a tabloid
cannot in general be expressed using a partition.
The column reading C(T ) of a tabloid T is the word in A∗ obtained
by proceeding through the columns, from leftmost to rightmost, and
reading each column from bottom to top. For example, the column
readings of the tableau (3.1) and the tabloid (3.2) are respectively
5421 6432 52 2 4 and 52 6431 4 5421 2 (where the spaces are simply for

10

ALAN J. CAIN AND ANTÓNIO MALHEIRO

clarity, to show readings of individual columns), as illustrated below:
1
2
4
5

2 2 2 4
3 5
4
6

2 1 4 1 2
5 3
2
4
4
6
5

Let w ∈ A∗ , and let w(1) · · · w(m) be the factorization of w into maximal
decreasing factors. Let Toid(w) be the tabloid whose h-th column has
height |w(h) | and is filled with the symbols of w(h) , for h = 1, . . . , m.
Then C(Toid(w)) = w. (Note that the notion of reading described
here is the one normally used in the study of Young tableaux and the
plactic monoid, and is the opposite of the ‘Japanese reading’ used in
the theory of crystals. Throughout the paper, definitions follow the
convention compatible with the reading defined here. The resulting
differences from the usual practices in crystal theory will be explicitly
noted.)
If w is the column reading of some Young tableau T , it is called a
tableau word. Note that not all words in A∗ are tableau words. For
example, 343 is not a tableau word, since

3 3
and 3 3 4 are the
4

only tableaux containing the correct symbols, and neither of these has
column reading 343. The word w is a tableau word if and only if
Toid(w) is a tableau.
The plactic monoid arises from an algorithm that computes a Young
tableau P(w) from a word w ∈ A∗ .
Algorithm 3.1 (Schensted’s algorithm).
Input: A Young tableau T and a symbol a ∈ A.
Output: A Young tableau T ← a.
Method:
(1) If a is greater than or equal to every entry in the topmost row
of T , add a as an entry at the rightmost end of T and output
the resulting tableau.
(2) Otherwise, let z be the leftmost entry in the top row of T that
is strictly greater than a. Replace z by a in the topmost row
and recursively insert z into the tableau formed by the rows of
T below the topmost. (Note that the recursion may end with
an insertion into an ‘empty row’ below the existing rows of T .)
Using an iterative form of this algorithm, one can start from a word
a1 · · · ak (where ai ∈ A) and compute a Young tableau P(a1 · · · ak ).
Essentially, one simply starts with the empty tableau and inserts the
symbols a1 , . . . , ak in order: However, the algorithm described below
also computes a standard Young tableau Q(a1 · · · ak ) that is used in

CRYSTALLIZING THE HYPOPLACTIC MONOID

11

the Robinson–Schensted–Knuth correspondence, which will shortly be
described:
Algorithm 3.2.
Input: A word a1 · · · ak , where ai ∈ A.
Output: A Young tableau P(a1 · · · ak ) and a standard Young tableau
Q(a1 · · · ak ).
Method: Start with an empty Young tableau P0 and an empty standard Young tableau Q0 . For each i = 1, . . . , k, insert the symbol ai
into Pi−1 as per Algorithm 3.1; let Pi be the resulting Young tableau.
Add a cell filled with i to the standard tableaux Qi−1 in the same place
as the unique cell that lies in Pi but not in Pi−1 ; let Qi be the resulting
standard Young tableau.
Output Pk for P(a1 · · · ak ) and Qk as Q(a1 · · · ak ).
For example, the sequence of pairs (Pi , Qi ) produced during the application of Algorithm 4.3 to the word 2213 is
( , ),



2 , 1 ,



2 2 , 1 2 ,

Therefore P(4323) =



1 2 1 2
,
2
3

 

1 2 3 1 2 4
,
,
.
2

3

1 2 3
1 2 4
and Q(4323) =
. It is straight2
3

forward to see that the map w 7→ P (w), Q(w) is a bijection between
words in A∗ and pairs consisting of a Young tableau over A and a
standard Young tableau of the same shape. This is the celebrated
Robinson–Schensted–Knuth correspondence (see, for example, [Ful97,
Ch. 4] or [Sta05, § 7.11].
The possible definition (approach P2 in the introduction) of the relation ≡plac using tableaux and insertion is the following:
u ≡plac v ⇐⇒ P(u) = P(v).
Using this as a definition, it follows that ≡plac is a congruence on A∗
[Knu70]. The factor monoid A∗ /≡plac is the plactic monoid and is
denoted plac. The relation ≡plac is the plactic congruence on A∗ . The
congruence ≡plac naturally restricts to a congruence on A∗n , and the
factor monoid A∗n /≡plac is the plactic monoid of rank n and is denoted
placn .
If w is a tableau word, then w = C(P(w)) and Toid(w) = P(w).
Thus the tableau words in A∗ form a cross-section (or set of normal
forms) for plac, and the tableau words in A∗n form a cross-section for
placn .

12

ALAN J. CAIN AND ANTÓNIO MALHEIRO

3.2. Kashiwara operators and the crystal graph. The following
discussion of crystals and Kashiwara operators is restricted to the context of placn . For a more general introduction to crystal bases, see
[CGM].
The Kashiwara operators ẽi and f˜i , where i ∈ {1, . . . , n − 1}, are
partially-defined operators on A∗n . In representation-theoretic terms,
the operators ẽi and f˜i act on a tensor product by acting on a single
tensor factor [HK02, § 4.4]. This action can be described in a combinatorial way using the the so-called signature or bracketing rule. This
paper describes the action directly using this rule, since the the analogous quasi-Kashiwara operators are defined by modifying this rule.
The definitions of ẽi and f˜i start from the crystal basis for placn ,
which will form a connected component of the crystal graph:
(3.3)

1

1

2

2

3

3

...

n−2

n−1 n−1 n

Each operator f˜i is defined so that it ‘moves’ a symbol a forwards along
a directed edge labelled by i whenever such an edge starts at a, and
each operator ẽi is defined so that it ‘moves’ a symbol a backwards
along a directed edge labelled by i whenever such an edge ends at a:
a i f˜i (a)
and ẽi (a)

i

a

Using the crystal basis given above, one sees that
ẽi (i + 1) = i,
f˜i (i) = i + 1,

ẽi (x) is undefined for x 6= i + 1;
f˜i (x) is undefined for x 6= i.

The definition is extended to A∗n \ An by the recursion
(
ẽi (u) v if ˜i (u) > φ̃i (v);
ẽi (uv) =
u ẽi (v) if ˜i (u) ≤ φ̃i (v),
(
f˜i (u) v if ˜i (u) ≥ φ̃i (v);
f˜i (uv) =
u f˜i (v) if ˜i (u) < φ̃i (v),

where ˜i and φ̃i are auxiliary maps defined by

˜i (w) = max k ∈ N ∪ {0} : ẽi · · · ẽi (w) is defined ;
| {z }
k times

˜
φ̃i (w) = max k ∈ N ∪ {0} : fi · · · f˜i (w) is defined .
| {z }
k times

Notice that this definition is not circular: the definitions of ẽi and f˜i
depend, via ˜i and φ̃i , only on ẽi and f˜i applied to strictly shorter words;
the recursion terminates with ẽi and f˜i applied to single letters from the
alphabet An , which was defined using the crystal basis (3.3). (Note that
this definition is in a sense the mirror image of [KN94, Theorem 1.14],

CRYSTALLIZING THE HYPOPLACTIC MONOID

length 0

length 1

ε

1

z}|{

z}|{

z

1

2

length 2

}|

11
1

12

21

2 1

2

3

13

13

{

2

22

31

1 2

1

23

32

2

z

33

length 3

}|

111
1

112

2 1

113

122

1 2 1

123

222

2 1 2

133

223

1 2

233

211

1 2

212

{

121

1 2

311

221

131

2

1

2

1

213

312

231

132

2

1

2

1

322

331

313

1 2

323

321

232

1 2

332

2

333

Figure 1. Part of the crystal graph for plac3 . Note that
each connected component consists of words of the same
length. In particular, the empty word ε is an isolated
vertex, and the words of length 1 form a single connected
component, which is the crystal basis for plac3 . The two
connected components whose highest-weight words are
211 and 121 are isomorphic. However, the components
consisting of the isolated vertex 321 is not.
because of the choice of definition for readings of tableaux used in this
paper. Thus the definition of ẽi and f˜i is the same as [Shi05, p. 8].)
Although it is not immediate from the definition, the operators ẽi
and f˜i are well-defined. Furthermore, ẽi and f˜i are mutually inverse
whenever they are defined, in the sense that if ẽi (w) is defined, then
w = f˜i (ẽi (w)), and if f˜i (w) is defined, then w = ẽi (f˜i (w)).
The crystal graph for placn , denoted Γ(placn ), is the directed labelled
graph with vertex set A∗n and, for w, w0 ∈ A∗n , an edge from w to w0
labelled by i if and only if w0 = f˜i (w) (or, equivalently, w = ẽi (w0 )).
Figure 1 shows part of the crystal graph Γ(plac3 ).

14

ALAN J. CAIN AND ANTÓNIO MALHEIRO

Since the operators ẽi and f˜i preserve lengths of words, and since
there are finitely many words in A∗n of each length, each connected
component in the crystal graph must be finite.
For any w ∈ A∗n , let Γ(placn , w) denote the connected component of
Γ(placn ) that contains the vertex w. Notice that the crystal basis (3.3)
is the connected component Γ(placn , 1).
A crystal isomorphism between two connected components is a weightpreserving labelled digraph isomorphism. That is, a map θ : Γ(placn , w) →
Γ(placn , w0 ) is a crystal isomorphism if it has the following properties:
• θ is bijective;
• wt(θ(u)) = wt(u) for all u ∈ Γ(placn , w);
i
v if and only
• for all u, v ∈ Γ(placn , w), there is an edge u
i θ(v)
if there is an edge θ(u)
.
The possible definition (approach P3 in the introduction) of the relation
≡plac using the crystal graph Γ(placn ) is the following: two words in A∗n
are related by ≡plac if and only if they lie in the same place in isomorphic
connected components. More formally, w ≡plac w0 if and only if there is
a crystal isomorphism θ : Γ(placn , w) → Γ(placn , w0 ) such that θ(w) =
w0 (see, for example, [Lec07]). For example, 2213 ≡plac 2231, and these
words appear in the same position in two of the connected components
shown in Figure 2. (This figure also illustrates other properties that
will be discussed shortly.)

3.3. Computing the Kashiwara operators. The recursive definition of the Kashiwara operators ẽi and f˜i given above is not particularly
convenient for practical computation. The following method, outlined
in [KN94], is more useful: Let i ∈ {1, . . . , n − 1} and let w ∈ A∗n . Form
a new word in {+, −}∗ by replacing each letter i of w by the symbol
+, each letter i + 1 by the symbol −, and every other symbol with the
empty word, keeping a record of the original letter replaced by each
symbol. Then delete factors −+ until no such factors remain: the resulting word is +φ̃i (w) −˜i (w) , and is denoted by ρi (w). Note that factors
+− are not deleted. (The method given in [KN94] involved deleting
factors +−; again, this difference is a consequence of the choice of
convention for reading tableaux.)
If ˜i (w) = 0, then ẽi (w) is undefined. If ˜i (w) > 0 then one obtains
ẽi (w) by taking the letter i + 1 which was replaced by the leftmost −
of ρi (w) and changing it to i. If φ̃i (w) = 0, then f˜i (w) is undefined.
If φ̃i (w) > 0 then one obtains f˜i (w) by taking the letter i which was
replaced by the rightmost + of ρi (w) and changing it to i + 1.
For a purely combinatorial proof that this method of computation
is correct, see [CGM, Proposition 2.1]. (Note that [CGM] uses the
tableaux-reading convention from representation theory, so that the
result must be reflected to fit the convention used here.)

CRYSTALLIZING THE HYPOPLACTIC MONOID

Γ(plac3 , 2111)
z
}|
{
111
2

Γ(plac3 , 1211)
z
}|
{
1211

1 2

15

Γ(plac3 , 1121)
z
}|
{
1121

1 2

112
2

111
3

122
2

113
2

112
3

2212 1213 1312

123
2

113
3

122
3

2213 1313 1322

133
2

123
3

222
3

2313 1323 2322

2331 1332 2232

133
3

223
3

3313 2323

3331 2332

1212 1311
1 2

2 1 2
2

|

{z

1 3 4
2

233
3

}

1

1 2

1 2

2 1 2

{z

1 2 4
3

3323

}

1

2231 1331 1232
2

1 2 1

2

1 2

|

1

2221 1231 1132

1

1 2 1

2

1221 1131

1 2
1 2

|

{z

3332

1 2 3
4

}

Figure 2. Three isomorphic components of the crystal graph for plac3 . In the component containing column readings of tableaux, the tableaux themselves are
shown instead of words. The standard tableaux below
each component is Q(w) for all words w in that component.
3.4. Properties of the crystal graph. In the crystal graph Γ(placn ),
the length of the longest path consisting of edges labelled by i ∈
{1, . . . , n − 1} that ends at w ∈ A∗n is ˜i (w). The length of the longest
path consisting of edges labelled by i that starts at w ∈ A∗n is φ̃i (w).
The operators ẽi and f˜i respectively increase and decrease weight
whenever they are defined, in the sense that if ẽi (w) is defined, then
wt(ẽi (w)) > wt(w), and if f˜i (w) is defined, then wt(f˜i (w)) < wt(w).
This is because ẽi replaces a symbol i + 1 with i whenever it is defined, which corresponds to decrementing the i + 1-th component and
incrementing the i-th component of the weight, which results in an increase with respect to the order (2.1). Similarly, f˜i replaces a symbol
i with i + 1 whenever it is defined. For this reason, the ẽi and f˜i are
respectively known as the Kashiwara raising and lowering operators.
Every connected component in Γ(placn ) contains a unique highestweight vertex: a vertex whose weight is higher than all other vertices in
that component. This means that no Kashiwara raising operator ẽi is
defined on this vertex. See [Shi05, § 2.4.2] for proofs and background.
(The existence, but not the uniqueness, of a highest-weight vertex is a
consequence of the finiteness of connected components.)

16

ALAN J. CAIN AND ANTÓNIO MALHEIRO

Whenever they are defined, the operators ẽi and f˜i preserve the property of being a tableau word and the shape of the corresponding tableau
[KN94]. Furthermore, all the tableau words corresponding to tableaux
of a given shape with entries in An lie in the same connected component. As shown in Figure 2, the left-hand component Γ(plac3 , 2111) is
made up of all the tableau words corresponding to tableaux of shape
(3, 1) with entries in A3 .
Each connected component in Γ(placn ) corresponds to exactly one
standard tableau, in the sense that Q(w) = Q(u) if and only if u and
w lies in the same connected component of Γ(placn ). In terms of the
bijection w 7→ (P(w), Q(w)) of the Robinson–Schensted–Knuth correspondence, specifying Q(w) locates the particular connected component Γ(placn , w), and specifying P(w) locates the word w within that
component.
Highest-weight words in Γ(placn ), and in particular highest-weight
tableau words, admit a useful characterization as Yamanouchi words.
A word w1 · · · wm ∈ A∗n (where wi ∈ An ) is a Yamanouchi word if,
for every j = 1, . . . , m, the weight of the suffix wj · · · wm is a nonincreasing sequence (that is, a partition). Thus 1231 is not a Yamanouchi word, since wt(31) = (1, 0, 1), but (1121) is a Yamanouchi
word, since wt(1121) = (3, 1, 0); wt(121) = (2, 1, 0); wt(21) = (1, 1, 0),
and wt(1) = (1, 0, 0). A word is highest-weight if and only if it is a
Yamanouchi word. See [Lot02, Ch. 5] for further background.
Highest-weight tableau words also have a neat characterization: a
tableau word is highest-weight if and only if its weight is equal to the
shape of the corresponding tableau. That is, a tableau word whose
corresponding tableau has shape λ is highest-weight if and only if, for
each i ∈ An , the number of symbols i it contains is λi . It follows that
a tableau whose reading is a highest-weight word must contain only
symbols i on its i-th row, for all i ∈ {1, . . . , `(λ)}. For example, the
tableau of shape (5, 3, 2, 2) whose reading is a highest-weight word is:
1
2
3
4

1 1 1 1
2 2
3
4

See [KN94] for further background.
4. Quasi-ribbon tableaux and insertion
This section gathers the relevant definitions and background on quasiribbon tableaux, the analogue of the Robinson–Schensted–Knuth correspondence, and the hypoplactic monoid. For further background, see
[KT97, Nov00].
Let α = (α1 , . . . , αm ) and β = (β1 , . . . , βp ) be compositions with
|α| = |β|. Then β is coarser than α, denoted β  α, if each partial

CRYSTALLIZING THE HYPOPLACTIC MONOID

17

sum β1 +. . .+βp0 (for p0 < p) is equal to some partial sum α1 +. . .+αm0
for some m0 < m. (Essentially, β is coarser than α if it can be formed
from α by ‘merging’ consecutive parts.) Thus (11)  (3, 8)  (3, 6, 2) 
(3, 1, 5, 2).
A ribbon diagram of shape α, where α is a composition, is an array of
boxes, with αh boxes in the h-th row, for h = 1, . . . , `(α) and counting
rows from top to bottom, aligned so that the leftmost cell in each row is
below the rightmost cell of the previous row. For example, the ribbon
diagram of shape (3, 1, 5, 2) is:
row 1

(4.1)

row 2
row 3
row 4

Notice that a ribbon diagram cannot contain a 2 × 2 subarray (that is,
of the form ).
In a ribbon diagram of shape α, the number of rows is `(α) and the
number of boxes is |α|.
A quasi-ribbon tableau of shape α, where α is a composition, is a
ribbon diagram of shape α filled with symbols from A such that the
entries in every row are non-decreasing from left to right and the entries
in every column are strictly increasing from top to bottom. An example
of a quasi-ribbon tableau is
(4.2)

1 2 2
3
4 4 5 5 5
6 7

Note the following immediate consequences of the definition of a quasiribbon tableau: (1) for each a ∈ A, the symbols a in a quasi-ribbon
tableau all appear in the same row, which must be the j-th row for
some j ≤ a; (2) the h-th row of a quasi-ribbon tableau cannot contain
symbols from {1, . . . , h − 1}.
A quasi-ribbon tabloid is a ribbon diagram filled with symbols from
A such that the entries in every column are strictly increasing from top
to bottom. (Notice that there is no restriction on the order of entries
in a row.) An example of a quasi-ribbon tabloid is
(4.3)

1 5 2
3
6 2 4 5 4
5 7

Note that a quasi-ribbon tableau is a special kind of quasi-ribbon
tabloid.
A recording ribbon of shape α, where α is a composition, is a ribbon
diagram of shape α filled with symbols from {1, . . . , |α|}, with each

18

ALAN J. CAIN AND ANTÓNIO MALHEIRO

symbol appearing exactly once, such that the entries in every row are
increasing from left to right, and entries in every column are increasing
from bottom to top. (Note that the condition on the order of entries
in rows is the same as in quasi-ribbon tableau, but the condition on
the order of entries in columns is the opposite of that in quasi-ribbon
tableau.) An example of a recording ribbon of shape (3, 1, 5, 2) is
(4.4)

1 2 9
8
3 4 6 7 11
5 10

The column reading C(T ) of a quasi-ribbon tabloid T is the word in
A obtained by proceeding through the columns, from leftmost to rightmost, and reading each column from bottom to top. For example, the
column reading of the quasi-ribbon tableau (4.2) and the quasi-ribbon
tabloid (4.3) are respectively 1 2 432 4 5 5 65 7 and 1 5 632 2 4 5 54 7 (where
the spaces are simply for clarity, to show readings of individual columns),
as illustrated below:
∗

1 2 2
3
4 4 5 5 5
6 7

1 5 2
3
6 2 4 5 4
5 7

Let w ∈ A∗ , and let w(1) · · · w(m) be the factorization of w into
maximal decreasing factors. Let QRoid(w) be the quasi-ribbon tabloid
whose h-th column has height |w(h) | and is filled with the symbols
of w(h) , for h = 1, . . . , m. (So each maximal decreasing factor of w
corresponds to a column of QRoid(w).) Then C(QRoid(w)) = w.
If w is the column reading of some quasi-ribbon tableau T , it is called
a quasi-ribbon word. It is easy to see that the word w is a quasi-ribbon
word if and only if QRoid(w) is a quasi-ribbon tableau. For example
433 is not a quasi-ribbon word, since QRoid(433) =

3
is the only
4 3

quasi-ribbon tabloid whose column reading is 433.
Proposition 4.1 ([Nov00, Proposition 3.4]). A word u ∈ A∗ is a
quasi-ribbon word if and only if std(u) is a quasi-ribbon word.
The following algorithm gives a method for inserting a symbol into
a quasi-ribbon tableau. It is due to Krob & Thibon, but is stated here
in a slightly modified form:
Algorithm 4.2 ([KT97, § 7.2]).
Input: A quasi-ribbon tableau T and a symbol a ∈ A.
Output: A quasi-ribbon tableau T ← a.

CRYSTALLIZING THE HYPOPLACTIC MONOID

19

Method: If there is no entry in T that is less than or equal to a,
output the quasi-ribbon tableau obtained by creating a new entry a
and attaching (by its top-left-most entry) the quasi-ribbon tableau T
to the bottom of a.
If there is no entry in T that is greater than a, output the word
obtained by creating a new entry a and attaching (by its bottom-rightmost entry) the quasi-ribbon tableau T to the left of a.
Otherwise, let x and z be the adjacent entries of the quasi-ribbon
tableau T such that x ≤ a < z. (Equivalently, let x be the right-most
and bottom-most entry of T that is less than or equal to a, and let z
be the left-most and top-most entry that is greater than a. Note that
x and z could be either horizontally or vertically adjacent.) Take the
part of T from the top left down to and including x, put a new entry a
to the right of x and attach the remaining part of T (from z onwards
to the bottom right) to the bottom of the new entry a, as illustrated
here:
x
z

x z

←a=

←a=

x a
z

x a
z

[where x and z are
vertically adjacent]
[where x and z are
horizontally adjacent]

Output the resulting quasi-ribbon tableau.
Using an iterative form of this algorithm, one can start from a
word a1 · · · ak (where ai ∈ A) and compute a quasi-ribbon tableau
QR(a1 · · · ak ). Essentially, one simply starts with the empty quasiribbon tableau and inserts the symbols a1 , a2 , . . . , ak in order. However, the algorithm described below also computes a recording ribbon
RR(a1 · · · ak ), which will be used later in discussing an analogue of the
Robinson–Schensted–Knuth correspondence.
Algorithm 4.3 ([KT97, § 7.2]).
Input: A word a1 · · · ak , where ai ∈ A.
Output: A quasi-ribbon tableau QR(a1 · · · ak ) and a recording ribbon
RR(a1 · · · ak ).
Method: Start with the empty quasi-ribbon tableau Q0 and an empty
recording ribbon R0 . For each i = 1, . . . , k, insert the symbol ai into
Qi−1 as per Algorithm 4.3; let Qi be the resulting quasi-ribbon tableau.
Build the recording ribbon Ri , which has the same shape as Qi , by
adding an entry i into Ri−1 at the same place as ai was inserted into
Qi−1 .
Output Qk for QR(a1 · · · ak ) and Rk as RR(a1 · · · ak ).

20

ALAN J. CAIN AND ANTÓNIO MALHEIRO

For example, the sequence of pairs (Qi , Ri ) produced during the application of Algorithm 4.3 to the word 4323 is
 




2
3
2
3

3 2
( , ), 4 , 1 ,
,
,  3 , 2 ,  3 3 , 2 4 .
4

1

2

4

1

4

1

3

Therefore QR(4323) = 3 3 and RR(4323) = 2 4 . It is straightfor4

1

ward to see that the map u 7→ (QR(u), RR(u)) is a bijection between
words in A∗ and pairs consisting of a quasi-ribbon tableau and a recording ribbon [KT97, § 7.2] of the same shape; this is an analogue of the
Robinson–Schensted–Knuth correspondence. For instace, if QR(u) is
(4.2) and RR(u) is (4.4), then u = 12446553275.
Recall the definition of DC( ) from Subsection 2.2.
Proposition 4.4 ([Nov00, Theorems 4.12 & 4.16]). For any word u ∈
A∗ , the shape of QR(u) (and of RR(u)) is DC(std(u)−1 ).

The possible definition (approach H2 in the introduction) of the relation ≡hypo using tableaux and insertion is the following:
u ≡hypo v ⇐⇒ QR(u) = QR(v).

Using this as a definition, it follows that ≡hypo is a congruence on
A∗ [Nov00], which is known as the hypoplactic congruence on A∗ . The
factor monoid A∗ /≡hypo is the hypoplactic monoid and is denoted hypo.
The congruence ≡hypo naturally restricts to a congruence on A∗n , and
the factor monoid A∗n /≡hypo is the hypoplactic monoid of rank n and
is denoted hypon .
As noted above, if w is a quasi-ribbon word, then w = C(QR(w)).
Thus the quasi-ribbon words in A∗ form a cross-section (or set of normal forms) for hypo, and the quasi-ribbon words in A∗n form a crosssection for hypon .
This paper also uses the following equivalent characterization of
≡hypo [Nov00, Theorem 4.18]:
u ≡hypo v ⇐⇒
(4.5)
DC(std(u)−1 ) = DC(std(v)−1 ) ∧ wt(u) = wt(v).
5. Quasi-Kashiwara operators and the quasi-crystal
graph
This section defines the quasi-Kashiwara operators and the quasicrystal graph, and shows that isomorphisms between components of
this graph give rise to a monoid. The following section will prove that
this monoid is in fact the hypoplactic monoid.
Let i ∈ {1, . . . , n − 1}. Let u ∈ A∗n . The word u has an i-inversion
if it contains a symbol i + 1 to the left of a symbol i. Equivalently, u

CRYSTALLIZING THE HYPOPLACTIC MONOID

21

has an i-inversion if it contains a subsequence (i + 1)i. (Recall from
Subsection 2.1 that a subsequence may be made up of non-consecutive
letters.) If the word u does not have an i-inversion, it is said to be
i-inversion-free.
Define the quasi-Kashiwara operators ëi and f¨i on A∗n as follows: Let
u ∈ A∗n .
• If u has an i-inverstion, both ëi (u) and f¨i (u) are undefined.
• If u is i-inversion-free, but u contains at least one symbol i + 1,
then ëi (u) is the word obtained from u by replacing the leftmost symbol i + 1 by i; if u contains no symbol i + 1, then ëi (u)
is undefined.
• If u is i-inversion-free, but u contains at least one symbol i,
then f¨i (u) is the word obtained from u by replacing the rightmost symbol i by i + 1; if u contains no symbol i, then f¨i (u) is
undefined.
For example,
ë2 (3123) is undefined since 3123 has a 2-inversion;
f¨2 (3131) is undefined since 3131 is 2-inversion free
but does not contains a symbol 2;
f¨1 (3113) = 3123.
Define


¨i (u) = max k ∈ N ∪ {0} : ëi · · · ëi (u) is defined ;
| {z }
k times

¨
φ̈i (u) = max k ∈ N ∪ {0} : fi · · · f¨i (u) is defined .
| {z }
k times

An immediate consequence of the definitions of ëi and f¨i is that:
• If u has an i-inverstion, then ¨i (u) = φ̈i (u) = 0;
• If u is i-inversion-free, then every symbol i lies to the left of
every symbol i + 1 in u, and so ¨i (u) = |u|i+1 and φ̈i (u) = |u|i .
Remark 5.1. It is worth noting how the quasi-Kashiwara operators ëi
and f¨i relate to the standard Kashiwara operators ẽi and f˜i as defined
in Subsection 3.2. As discussed in Subsection 3.3, one computes the
action of ẽi and f˜i on a word u ∈ A∗n by replacing each symbol i with
+, each symbol i + 1 with −, every other symbol with the empty word,
and then iteratively deleting factors −+ until a word of the form +p −q
remains, whose left-most symbol − and right-most symbol + (if they
exist) indicate the symbols in u changed by ẽi and f˜i respectively. The
deletion of factors −+ corresponds to rewriting to normal form a word
representing an element of the bicyclic monoid h +, − | (−+, ε) i. To
compute the action of the quasi-Kashiwara operators ëi and f¨i defined

22

ALAN J. CAIN AND ANTÓNIO MALHEIRO

above on a word u ∈ A∗n , replace the symbols in the same way as
before, but now rewrite to normal form as a word representing an
element of the monoid h +, − | (−+, 0) i, where 0 is a multiplicative
zero. Any word that contains a symbol − to the left of a symbol +
will be rewritten to 0 and so ëi and f¨i will be undefined in this case.
If the word does not contain a symbol − to the left of a symbol +,
then it is of the form +p −q , and the left-most symbol − and the rightmost symbol + indictate the symbols in u changed by ëi and f¨i . In
essence, one obtains the required analogies of the Kashiwara operators
by replacing the bicyclic monoid h +, − | (−+, ε) i, where −+ rewrites
to the identity, with the monoid h +, − | (−+, 0) i, where −+ rewrites
to the zero.
The action of the quasi-Kashiwara operators is essentially a restriction of the action of the Kashiwara operators:
Proposition 5.2. Let u ∈ A∗n . If ëi (u) is defined, so is ẽi (u), and
ẽi (u) = ëi (u). If f¨i (u) is defined, so is f˜i (u), and f˜i (u) = f¨i (u).
Proof. Let u ∈ A∗n . Suppose the quasi-Kashiwara operator ëi is defined
on u. Then u contains at least one symbol i + 1 but is i-inversion-free,
so that every symbol i lies to the left of every symbol i + 1 in u. So
when one computes the action of ẽi , replacing every symbol i with the
symbol + and every symbol i + 1 with the symbol − leads immediately
to the word +φ̃i (u) −˜i (u) (that is, there are no factors −+ to delete).
Hence ˜i (u) > 0, and so the Kashiwara operator ẽi is defined on u.
Furthermore, ẽi acts by changing the symbol i + 1 that contributed the
leftmost − to i, and, since there was no deletion of factors −+, this
symbol must be the leftmost symbol i + 1 in u. Thus ẽi (u) = ëi (u).
Similarly, if the quasi-Kashiwara operator f¨i is defined on u, so is
the Kashiwara operator f˜i , and f˜i (u) = f¨i (u).

The original definition of the Kashiwara operators ẽi and f˜i in Subsection 3.2 was recursive: whether the action on uv recurses to the
action on u or on v depends on the maximum number of times each
operator can be applied to u and v separately. It seems difficult to
give a similar recursive definition for the quasi-Kashiwara operators ëi
and f¨i defined here: if, for example, both operators can be applied zero
times to u, this may mean that u does not contain symbols i or i + 1,
in which case the operators may still be defined on uv, or it may mean
that u contains a symbol i + 1 to the left of a symbol i, in which case
the operators are certainly not defined on uv.
This concludes the discussion contrasting the standard Kashiwara
operators with the quasi-Kashiwara operators defined here. The aim
now is to use the operators ëi and f¨i to build the quasi-crystal graph
and to establish some of its properties.

CRYSTALLIZING THE HYPOPLACTIC MONOID

23

Lemma 5.3. For all i ∈ {1, . . . , n − 1}, the operators ëi and f¨i are
mutually inverse, in the sense that if ëi (u) is defined, u = f¨i (ëi (u)),
and if f¨i (u) is defined, u = ëi (f¨i (u)).
Proof. Let u ∈ A∗n . Suppose that ëi (u) is defined. Then u contains
at least one symbol i + 1 but is i-inversion-free, so that every symbol
i + 1 is to the right of every symbol i. Since ëi (u) is obtained from u by
replacing the left-most symbol i+1 by i (which becomes the right-most
symbol i), every symbol i + 1 is to the right of every symbol i in the
word ëi (u) and so ëi (u) is i-inversion-free, and ëi (u) contains at least
one symbol i. Thus f¨i (ëi (u)) is defined, and is obtained from ëi (u) by
replacing the right-most symbol i by i + 1, which produces u. Hence if
ëi (u) is defined, u = f¨i (ëi (u)). Similar reasoning shows that if f¨i (u) is
defined, u = ëi (f¨i (u)).

The operators ëi and f¨i respectively increase and decrease weight
whenever they are defined, in the sense that if ëi (u) is defined, then
wt(ëi (u)) > wt(u), and if f¨i (u) is defined, then wt(f¨i (u)) < wt(u). This
is because ëi replaces a symbol i+1 with i whenever it is defined, which
corresponds to decrementing the i + 1-th component and incrementing
the i-th component of the weight, which results in an increase with
respect to the order (2.1). Similarly, f¨i replaces a symbol i with i + 1
whenever it is defined. For this reason, the ëi and f¨i are respectively
called the quasi-Kashiwara raising and lowering operators.
The quasi-crystal graph Γn is the labelled directed graph with vertex
set A∗n and, for all u ∈ A∗n and i ∈ {1, . . . , n − 1}, an edge from
u to u0 labelled by i if and only if f¨i (u) = u0 (or, equivalently by
Lemma 5.3, u = ëi (u0 )). Part of Γ4 is shown in Figure 3. (The notation
Γn will be discarded in favour of Γ(hypon ) after it has been shown that
the relationship between Γn and hypon is analogous to that between
Γ(placn ) and placn .)
For any u ∈ A∗n , let Γn (u) be the connected component of Γn containing the vertex u. Notice that every vertex of Γn has at most one
incoming and at most one outgoing edge with a given label. A quasicrystal isomorphism between two connected components is a weightpreserving labelled digraph isomorphism. (This parallels the definition
of a crystal isomorphism in Subsection 3.2.)
Define a relation ∼ on the free monoid A∗n as follows: u ∼ v if
and only if there is a quasi-crystal isomorphism θ : Γn (u) → Γn (v)
such that θ(u) = v. That is, u ∼ v if and only if u and v are in
the same position in isomorphic connected components of Γn . For
example, 1324 ∼ 3142, since these words are in the same position in
their connected components, as can be seen in Figure 3.
The rest of this section is dedicated to proving that the relation ∼ is a
congruence on A∗n . The proofs of this result and the necessary lemmata

24

ALAN J. CAIN AND ANTÓNIO MALHEIRO

1212

2121

2

2

1213
2

2131
3

1313
1

1214
3

1323
1

3

1

2434
2

3434

3

1424
1

2424
2

1

2

1434
1

2141
3

3132
3

1324

2324
3

2

1

3

3131

1314

2323
3

2

1

1414
1

3141
3

3232
3

1

3

3

4141
1

4142
1

4242
2

1

3142

3242
3

2

2

4143
1

4243
2

4343

Figure 3. The isomorphic components Γ4 (1212) and
Γ4 (2121) of the quasi-crystal graph Γ4 .
parallel the purely combinatorial proofs by the present authors and
Gray [CGM, § 2.4] that isomorphisms of crystal graphs give rise to
congruences.
Lemma 5.4. Let u, v, u0 , v 0 ∈ A∗n . Suppose u ∼ v and u0 ∼ v 0 , and
let θ : Γn (u) → Γn (v) and θ0 : Γn (u0 ) → Γn (v 0 ) be quasi-crystal isomorphisms such that θ(u) = v and θ0 (u0 ) = v 0 . Let i ∈ {1, . . . , n − 1}.
Then:
(1) ëi (uu0 ) is defined if and only if ëi (vv 0 ) is defined. If both are
defined, exactly one of the following statements holds:
(a) ëi (uu0 ) = uëi (u0 ) and ëi (vv 0 ) = vëi (v 0 );
(b) ëi (uu0 ) = ëi (u)u0 and ëi (vv 0 ) = ëi (v)v 0 .

CRYSTALLIZING THE HYPOPLACTIC MONOID

25

(2) f¨i (uu0 ) is defined if and only if f¨i (vv 0 ) is defined. If both are
defined, exactly one of the following statements holds:
(a) f¨i (uu0 ) = uf¨i (u0 ) and f¨i (vv 0 ) = v f¨i (v 0 );
(b) f¨i (uu0 ) = f¨i (u)u0 and f¨i (vv 0 ) = f¨i (v)v 0 .
Proof. Suppose ëi (uu0 ) is defined. Then uu0 is i-inversion-free, and
contains at least one symbol i + 1. Hence both u and u0 are i-inversionfree, and at least one of u and u0 contains a symbol i + 1. Since θ and
θ0 are crystal isomorphisms, wt(u) = wt(v) and wt(u0 ) = wt(v 0 ) (and
thus u and v contain the same number of each symbol, and u0 and v 0
contain the same number of each symbol). Consider separately two
cases depending on whether u contains a symbol i + 1:
• Suppose that u does not contain a symbol i + 1 (and hence
v does not contain a symbol i + 1). Then u0 must contain a
symbol i + 1 and indeed the left-most symbol i + 1 of uu0 must
lie in u0 . So ëi (u0 ) is defined and ëi (uu0 ) = uëi (u0 ). Thus there
is an edge labelled by i ending at u0 . Since θ0 is a quasi-crystal
isomorphism, there is an edge labelled by i ending at v 0 . Hence
ëi (v 0 ) is defined, and so v 0 is i-inversion-free. Since v does not
contain any symbol i + 1, it follows that vv 0 is i-inversion-free.
Hence ëi (vv 0 ) is defined and, since the left-most symbol i + 1 of
vv 0 lies in v 0 , it also holds that ëi (vv 0 ) = vëi (v 0 ).
• Suppose that u contains a symbol i + 1 (and hence v contains
a symbol i + 1). Then u0 cannot contain a symbol i, and the
left-most symbol i + 1 of uu0 must lie in u. Then ëi (u) is defined
and ëi (uu0 ) = ëi (u)u0 . So there is an edge labelled by i ending
at u. Since θ is a quasi-crystal isomorphism, there is an edge
labelled by i ending at v. Hence ëi (v) is defined, and so v is iinversion-free. Since v 0 does not contain any symbol i, it follows
that vv 0 is i-inversion-free. Hence ëi (vv 0 ) is defined and, since
the left-most symbol i + 1 in vv 0 lies in v, it also holds that
ëi (vv 0 ) = ëi (v)v 0 .
This proves the forward implications of the three statements relating to
ëi in part (1). Interchanging u and u0 with v and v 0 proves the reverse
implications. The statements for f¨i in part (2) follow similarly.

Lemma 5.5. Let u, v, u0 , v 0 ∈ A∗n . Suppose u ∼ v and u0 ∼ v 0 , and let
θ : Γn (u) → Γn (v) and θ0 : Γn (u0 ) → Γn (v 0 ) be quasi-crystal 
isomor0 0
0
phisms such that θ(u) = v and θ (u ) = v . Let g̈i1 , . . . , g̈ir ∈ ëi , f¨i :
i ∈ {1, . . . , n − 1} . Then:
(1) g̈i1 · · · g̈ir (uu0 ) is defined if and only if g̈i1 · · · g̈ir (vv 0 ) is defined.
(2) When both g̈i1 · · · g̈ir (uu0 ) and g̈i1 · · · g̈ir (vv 0 ) are defined, the sequence g̈i1 , . . . , g̈ir partitions into two subsequences g̈j1 , . . . , g̈js

26

ALAN J. CAIN AND ANTÓNIO MALHEIRO

and g̈k1 , . . . , g̈kt such that
g̈i1 · · · g̈ir (uu0 ) = g̈j1 · · · g̈js (u)g̈k1 · · · g̈kt (u0 ),
g̈i1 · · · g̈ir (vv 0 ) = g̈j1 · · · g̈js (v)g̈k1 · · · g̈kt (v 0 );

where

θ g̈j1 · · · g̈js (u) = g̈j1 · · · g̈js (v),

θ0 g̈k1 · · · g̈kt (u0 ) = g̈k1 · · · g̈kt (v 0 ).

Proof. This result follows by iterated application of Lemma 5.4, with
the last two equalities holding because θ and θ0 are quasi-crystal isomorphisms with θ(u) = v and θ0 (u0 ) = v 0 .

Proposition 5.6. The relation ∼ is a congruence on the free monoid
A∗n .

Proof. It is clear from the definition that ∼ is an equivalence relation;
it thus remains to prove that ∼ is compatible with multiplication in
A∗n .
Suppose u ∼ v and u0 ∼ v 0 . Then there exist quasi-crystal isomorphisms θ : Γn (u) → Γn (v) and θ : Γn (u0 ) → Γn (v 0 ) such that θ(u) = v
and θ0 (u0 ) = v 0 .
Define a map Θ :Γn (uu0 ) → Γn (vv 0 ) as follows. For w ∈ Γn (uu0 ),
choose g̈i1 , . . . , g̈ir ∈ ëi , f¨i : i ∈ {1, . . . , n−1} such that g̈i1 · · · g̈ir (uu0 ) =
w; such a sequence exists because w lies in the connected component
Γn (uu0 ). Define Θ(w) to be g̈i1 · · · g̈ir (vv 0 ); note that this is defined by
Lemma 5.5(1).
 It is necessary to prove that Θ is well-defined. Suppose0 that g̈ı̂1 , . . . , g̈ı̂m ∈
ëi , f¨i : i ∈ {1, . . . , n − 1} is such that g̈ı̂1 · · · g̈ı̂m (uu ) = w, and let
z = g̈ı̂1 · · · g̈ı̂m (vv 0 ). Note that by Lemma 5.5(2),
• the sequence g̈i1 , . . . , g̈ir partitions into two subsequences g̈j1 , . . . , g̈js
and g̈k1 , . . . , g̈kt such that
(5.1)

g̈i1 · · · g̈ir (uu0 ) = g̈j1 · · · g̈js (u)g̈k1 · · · g̈kt (u0 );

• the sequence g̈ı̂1 , . . . , g̈ı̂m partitions into two subsequences g̈̂1 , . . . , g̈̂p
and g̈k̂1 , . . . , g̈k̂q such that
(5.2)

g̈ı̂1 · · · g̈ı̂m (uu0 ) = g̈̂1 · · · g̈̂p (u)g̈k̂1 · · · g̈k̂q (u0 ).

Since both g̈i1 · · · g̈ir (uu0 ) and g̈ı̂1 · · · g̈ı̂m (uu0 ) equal w, and since g̈j1 · · · g̈js (u)
and g̈̂1 · · · g̈̂p (u) have length |u|, it follows that
(5.3)
Then

g̈j1 · · · g̈js (u) = g̈̂1 · · · g̈̂p (u);

g̈k1 · · · g̈kt (u0 ) = g̈k̂1 · · · g̈k̂q (u0 ).
Θ(w) = g̈i1 · · · g̈ir (vv 0 )

= g̈j1 · · · g̈js (v)g̈k1 · · · g̈kt (v 0 )

[by definition]
[by (5.1)]

CRYSTALLIZING THE HYPOPLACTIC MONOID



= θ g̈j1 · · · g̈js (u) θ0 g̈k1 · · · g̈kt (u0 )


= θ g̈̂1 · · · g̈̂p (u) θ0 g̈k̂1 · · · g̈k̂q (u0 )
= g̈̂1 · · · g̈̂p (v)g̈k̂1 · · · g̈k̂q (v 0 )

= g̈ı̂1 · · · g̈ı̂m (vv 0 )
= z.

27

[by (5.3)]
[by (5.2)]

So Θ is well-defined.
By Lemma 5.5(1), Θ and its inverse preserve labelled edges. To see
that Θ preserves weight, proceed as follows. Since θ and θ0 are quasicrystal isomorphisms, wt(u) = wt(v) and wt(u0 ) = wt(v 0 ). Hence
wt(uu0 ) = wt(vv 0 ). Therefore if g̈i1 · · · g̈ir (uu0 ) and g̈i1 · · · g̈ir (vv 0 ) are
both defined, then both sequences of operators partition as above, and
so

wt(w) = wt g̈i1 · · · g̈ir (uu0 )

= wt g̈j1 · · · g̈js (u)g̈k1 · · · g̈kt (u0 )


= wt g̈j1 · · · g̈js (u) + wt g̈k1 · · · g̈kt (u0 )


= wt θ(g̈j1 · · · g̈js (u)) + wt θ0 (g̈k1 · · · g̈kt (u0 ))
[since θ and θ0 preserve weights]


= wt g̈j1 · · · g̈js (θ(u)) + wt g̈k1 · · · g̈kt (θ0 (u0 ))

[since θ and θ0 are quasi-crystal isomorphisms]


= wt g̈j1 · · · g̈js (v) + wt g̈k1 · · · g̈kt (v 0 )

= wt g̈j1 · · · g̈js (v)g̈k1 · · · g̈kt (v 0 )

= wt g̈i1 · · · g̈ir (vv 0 )
= wt(Θ(w)).

Thus Θ is a quasi-crystal isomorphism. Hence uu0 ∼ vv 0 . Therefore
the relation ∼ is a congruence.

6. The quasi-crystal graph and the hypoplactic monoid
Since ∼ is a congruence, it makes sense to define the factor monoid
Hn = A∗n /∼. The aim is now to show that Hn is the hypoplactic monoid
hypon by showing that ∼ is equal to the relation ≡hypo on A∗n as defined
in Section 4 using quasi-ribbon tableaux and Algorithm 4.3. Some of
the lemmata in this section are more complicated than necessary for
this aim, because they will be used in future sections to prove other
results.
Proposition 6.1. Let u ∈ A∗n and i ∈ {1, . . . , n − 1}.
(1) If ëi (u) is defined, then std(ëi (u)) = std(u).
(2) If f¨i (u) is defined, then std(f¨i (u)) = std(u).

28

ALAN J. CAIN AND ANTÓNIO MALHEIRO

Proof. Suppose ëi (u) is defined, and that u contains σ symbols i and τ
symbols i + 1. Then during the computation of std(u), these symbols
i and i + 1 become i1 , . . . , iσ and (i + 1)1 , . . . , (i + 1)τ when subscripts
are attached. Since ëi (u) is defined, u is i-inversion-free and so every
symbol i in u is to the left of every symbol i + 1, and ëi (u) is obtained
from u by replacing the leftmost symbol i + 1 by i. Thus, during the
computation of std(ëi (u)), the symbols i and i + 1 become i1 , . . . , iσ+1
and (i+1)1 , . . . , (i+1)τ −1 . Thus, symbols i1 , . . . , iσ , (i+1)1 , . . . , (i+1)τ
and i1 , . . . , iσ+1 , (i+1)1 , . . . , (i+1)τ −1 are replaced by the same symbols
of the same rank in A. Hence std(ëi (u)) = std(u). This proves part (1);
similar reasoning proves part (2).

Corollary 6.2. If u ∈ A∗n is a quasi-ribbon word, then every word in
Γn (u) is quasi-ribbon word, and all of the corresponding quasi-ribbon
tableaux have the same shape as QR(u).
Proof. Let w ∈ Γn (u). By Proposition 6.1, std(w) = std(u). Thus
by Proposition 4.1, w is a quasi-ribbon word, and by Proposition 4.4,
QR(w) has the same shape as QR(u).

Lemma 6.3. Let i ∈ {1, . . . , n − 1}. Let u ∈ A∗n be a quasi-ribbon
word. Then:
(1) ëi (u) is defined if and only if QR(u) contains some symbol i + 1
but does not contain i + 1 below i in the same column;
(2) f¨i (u) is defined if and only if QR(u) contains some symbol i but
does not contain i + 1 below i in the same column.
Proof. By the definition of the reading of a quasi-ribbon tableau, and
the fact that the rows of quasi-ribbon tableaux are non-decreasing from
left to right, the word u has an i-inversion if and only if i+1 and i appear
in the same column of QR(u). Thus part (1) follows immediately from
the definition of ëi . Part (2) follows by similar reasoning for f¨i .

Proposition 6.4. Let α be a composition.
(1) The set of quasi-ribbon words corresponding to quasi-ribbon tableaux
of shape α forms a single connected component of Γn .
(2) In this connected component, there is a unique highest-weight
word, which corresponds to the quasi-ribbon tableau of shape α
whose j-th row consists entirely of symbols j, for j = 1, . . . , `(α).
Proof. Let w be the quasi-ribbon word such that QR(w) has shape α
and has j-th row full of symbols j, for each j = 1, . . . , `(α). Clearly
ëi (w) cannot be defined for any i ≥ `(α), since there are no symbols
i+1 in the word w. Furthermore, for i = 1, . . . , `(α)−1, the right-most
entry i in the i-th row of T lies immediately above the left-most entry
i + 1 in the i + 1-th row. Thus, by Lemma 6.3, ëi (w) is not defined.
Hence w is highest-weight. (Note that it is still necessary to show that
w is the unique highest-weight word in its connected component of Γn .)

CRYSTALLIZING THE HYPOPLACTIC MONOID

29

Let u be a quasi-ribbon word such that QR(u) has shape α but has
the property that the j-th row does not consist entirely of symbols j,
for at least one j ∈ {1, . . . , `(α)}. Thus there is some symbol i that
appears in the h-th row, where h < i. Without loss of generality,
assume i is minimal. Clearly i > 1 since h ≥ 1. Consider two cases:
• The left-most symbol in the h-th row is i. Then, by the minimality of i, the symbol i − 1 cannot appear in u, for it would
have to appear on the h − 1-row of QR(u). Thus u does not
contain a symbol i − 1; hence ëi−1 (u) is defined.
• The left-most symbol in the h-th row is not i. Then every
symbol i − 1 in QR(u) must appear in a column strictly to the
left of the left-most symbol i. Hence, by Lemma 6.3, ëi−1 (u) is
defined.
Thus some quasi-Kashiwara operator ëi can be applied to u and so u
is not a highest-weight word.
This implies that w is the unique highest-weight quasi-ribbon word
that has shape α. Furthermore, by Corollary 6.2, applying ëi raises
the weight of a word but maintains the property of being a quasiribbon word and the shape α of its corresponding quasi-ribbon tableau.
Therefore some sequence of operators ëi must transform the word u to
the word w. Thus the set of quasi-ribbon words whose corresponding
quasi-ribbon tableau have shape α forms a connected component. 
Thus, for example, the highest-weight quasi-ribbon word corresponding to a quasi-ribbon tableau of shape (3, 1, 5, 2) is 11321333434, corresponding to the quasi-ribbon tableau
1 1 1
2
3 3 3 3 3
4 4

See also Figures 3 and 4, where the connected component Γ4 (1212),
shown on the left, consists entirely of quasi-ribbon words corresponding
to quasi-ribbon tableaux of shape (2, 2), and its unique highest-weight
word is 1212.
Note that Proposition 6.4(2) only establishes the existence of unique
highest-weight words in connected components consisting of quasiribbon words, and not in every component.
Corollary 6.5. Let α be a composition, and let w be a quasi-ribbon
word such that QR(w) has shape α. Then w is a highest-weight word
if and only if wt(w) = α.
Proof. Suppose w is a highest-weight word. By Proposition 6.4(2), the
j-th row of QR(w) consists entirely of symbols j, for j = 1, . . . , `(α).
Thus w contains exactly αj symbols j for each j, and so wt(w) = α.

30

ALAN J. CAIN AND ANTÓNIO MALHEIRO

1 1
2 2

2121

2

2

1 1
2 3
2

2131
3

1 1
3 3
1

1 1
2 4
3

1 2
3 3
1

3

1

2 3
4 4
2
3 3
4 4

3
1 2
4 4

1

2 2
4 4
2

1

2
1 3
4 4

1

2141
3

3132
3

1 2
3 4

2 2
3 4
3

2

1

3

3131

1 1
3 4

2 2
3 3
3

2

1
1 1
4 4

1

3141
3

3232
3

1

3

3

4141
1

4142
1

4242
2

1

3142

3242
3

2

2

4143
1

4243
2

4343

Figure 4. The isomorphic components Γ4 (1212) (left)
and Γ4 (2121) (right) of the quasi-crystal graph Γ4 , with
elements of Γ4 (1212) drawn as quasi-ribbon tableau instead of written as words. The component Γ4 (1212)
consists of all quasi-ribbon words whose quasi-ribbon
tableaux have shape (2, 2). None of the words in Γ4 (2112)
is a quasi-ribbon word.
Now suppose that wt(w) = α. In a quasi-ribbon tableau, a symbol
j can only appear in rows 1 to j. Hence the α1 symbols 1 in QR(w)
must appear in row 1, which has length α1 , so this row is full of symbols 1. The α2 symbols 2 must appear in rows 1 and 2, but row 1 is
full of symbols 1, so row 2, which has length α2 , is full of symbols 2.
Continuing in this way, row j, which has length αj , is full of symbols
j. By Proposition 6.4(2), w is a highest-weight word.


CRYSTALLIZING THE HYPOPLACTIC MONOID

31

Corollary 6.6. Let u, v ∈ A∗n be highest-weight quasi-ribbon words. If
wt(u) = wt(v), then u = v.
Proof. By Corollary 6.5, since u and v are highest-weight, QR(u) has
shape wt(u) and QR(v) has shape wt(v). Since these weights are equal,
QR(u) and QR(v) have the same shape. By the characterization of
highest-weight words in Proposition 6.4(2), it follows that u = v. 
Proposition 6.7. There is at most one quasi-ribbon word in each ∼class.
Proof. Suppose u, v ∈ A∗n are quasi-ribbon words with u ∼ v. By
Proposition 6.4, there is a sequence of operators ëi1 , . . . , ëik such that
u0 = ëi1 · · · ëik (u) is highest-weight. Since u ∼ v implies that the words
u and v are at the same location in the isomorphic components Γn (u)
and Γn (v), the word v 0 = ëi1 · · · ëik (v) is also highest-weight. The
isomorphism from Γn (u) to Γn (v) preserves weight, and so wt(u) =
wt(v). Thus u = v by Corollary 6.6.

Proposition 6.7 shows that each element of Hn = A∗n /∼ has at most
one representative as a quasi-ribbon word. The aim is now to show
that if two words are ≡hypo -related, then they are ∼-related, which will
establish a one-to-one correspondence between the elements of Hn and
quasi-ribbon tableaux:
Lemma 6.8. Let u ∈ A∗n . Then u and C(QR(u)) have exactly the
same labelled edges incident to them in Γn .
Proof. The aim is to prove that ëi (u) is defined if and only if ëi (C(QR(u)))
is defined. Similar reasoning shows that f¨i (u) is defined if and only if
f¨i (C(QR(u))) is defined.
First, note that since u ≡hypo C(QR(u)), it follows from (4.5) that
wt(u) = wt(C(QR(u))). Suppose ëi (u) is defined. Then u contains a
symbol i+1 but is i-inversion-free. Hence every symbol i is to the left of
every symbol i + 1 in u. Therefore Algorithm 4.3 appends the symbols
i + 1 to the right of any symbols i. Hence by Lemma 6.3, ëi (C(QR(u)))
is defined. On the other hand, suppose that ëi (C(QR(u))) is defined.
Then by Lemma 6.3, C(QR(u)) contains a symbol i+1, but no symbol i
immediately above i + 1 in a column. Hence the computation of QR(u)
using Algorithm 4.3 cannot involve inserting a symbol i later than a
symbol i + 1. That is, u is i-inversion-free. Since QR(u) contains a
symbol i + 1, so does u, and thus ëi (u) is defined.

Lemma 6.9. Let u ∈ A∗n and i ∈ {1, . . . , n − 1}.
(1) Suppose that ëi (u) is defined. Then ëi (u) ≡hypo ëi (C(QR(u)))
and so ëi (C(QR(u))) = C(QR(ëi (u))).
(2) Suppose that f¨i (u) is defined. Then f¨i (u) ≡hypo f¨i (C(QR(u)))
and so f¨i (C(QR(u))) = C(QR(f¨i (u))).

32

ALAN J. CAIN AND ANTÓNIO MALHEIRO

Proof. Suppose that ëi (u) is defined. Then it follows from Lemma 6.8
that ëi (C(QR(u))) is also defined. Now, u ≡hypo C(QR(u)) by the definition of ≡hypo . Thus it follows from (4.5) that wt(u) = wt(C(QR(u)))
and so wt(ëi (u)) = wt(ëi (C(QR(u)))) since ëi replaces one symbol i + 1
by a symbol i in both words. Further, it again follows from (4.5)
that DC(std(u)−1 ) = DC(std(C(QR(u)))−1 ). Hence, since ëi preserves
standardizations by Proposition 6.1, it follows that DC(std(ëi (u))−1 ) =
DC(std(ëi (C(QR(u))))−1 ). Combining this with the equality of weights
and using (4.5) again shows that ëi (u) ≡hypo ëi (C(QR(u))).
By Corollary 6.2, ëi (C(QR(u))) is a quasi-ribbon word. Since it is
≡hypo -related to ëi (u), it follows that ëi (C(QR(u))) = C(QR(ëi (u))).
This completes the proof of part (1); similar reasoning proves part (2).

Proposition 6.10. Let u, v ∈ A∗n . Then u ≡hypo v =⇒ u ∼ v.

Proof. By Lemmata 6.8 and 6.9, the map Θ : Γn (u) → Γn (C(QR(u)))
with Θ(w) = C(QR(w)) (for w ∈ Γn (u)) is a quasi-crystal isomorphism,
and so u ∼ C(QR(u)). Similarly, v ∼ C(QR(v)). It follows from
u ≡hypo v that QR(u) = QR(v). Since ∼ is transitive, u ∼ v.


Let u ∈ A∗n . By Proposition 6.10, QR(u) is a quasi-ribbon word that
is ∼-related to u. By Proposition 6.7, QR(u) is the unique quasi-ribbon
word that is ∼-related to u. Thus the following result has been proven:
Theorem 6.11. Let u, v ∈ A∗n . Then u ≡hypo v ⇐⇒ u ∼ v.
Corollary 6.12. hypon = A∗n /≡hypo ' A∗n /∼ = Hn .

In light of this, henceforth the quasi-crystal graph Γn is denoted
Γ(hypon ), and the connected component Γn (w) is denoted Γ(hypon , w)
Before moving on to study how the quasi-crystal graph interacts with
the hypoplactic version of the Robinson–Schensted–Knuth correspondence, it is necessary to prove one more fundamental property of the
quasi-crystal graph. Proposition 6.4(2) showed that the connected components comprising quasi-ribbon words contain unique highest-weight
words. The same holds for all connected components:
Proposition 6.13. In every connected component in Γ(hypon ) there
is a unique highest-weight word.
Proof. Let u ∈ A∗n . Since u ∼ C(QR(u)), the connected component Γ(hypon , u) is isomorphic to Γ(hypon , C(QR(u))). By Proposition
6.4(2), there is a unique highest-weight word in Γ(hypon , C(QR(u))).
Consequently, Γ(hypon , u) contains a unique highest-weight word. 
In the crystal graph of the plactic monoid (that is the plactic monoid
of type An ), the highest-weight words are characterized combinatorially
as follows. Recall from Subsection 3.4 that a Yamanouchi word is a
word w in A∗n such for any suffix v of w, it holds that |v|1 ≥ |v|2 ≥

CRYSTALLIZING THE HYPOPLACTIC MONOID

33

. . . ≥ |v|n . The highest-weight words in the crystal graph of the plactic
monoid are precisely the Yamanouchi words [Lot02, § 5.5].
Yamanouchi words do not characterize highest-weight words in connected components of the quasi-crystal graph Γ(hypon ). For example,
the highest-weight word in Γ(hypon , 2112) is 2112, which has the suffix
v = 2 that does not satisfy |v|1 ≥ |v|2 .
Let max(u) denote the largest symbol in the word u.
Proposition 6.14. A word u ∈ A∗n is highest-weight in a component of
Γ(hypon ) if and only if it contains all symbols in {1, . . . , max(u)}, with
the condition that it has an i-inversion for all i ∈ {1, . . . , max(u) − 1}.
Proof. These are precisely the words for which all operators ëi are undefined.

In the crystal graph Γ(placn ), suffixes of highest-weight words are
also highest-weight; this is an immediate consequence of the definition
of a Yamanouchi word. This does not hold in Γ(hypon ): the highestweight word 2112 has the suffix 2, which is not highest-weight.
7. The quasi-crystal graph and the
Robinson–Schensted–Knuth correspondence
The previous sections constructed the quasi-crystal graph Γ(hypon )
and showed that the hypoplactic congruence ≡hypo corresponds to quasicrystal isomorphisms (that is, weight-preserving labelled digraph isomorphisms) between its connected components, just as the plactic congruence ≡plac corresponds to crystal isomorphisms (that is, weightpreserving labelled digraph isomorphisms) between connected components of the crystal graph Γ(placn ). The following result shows that
the interaction of the quasi-crystal graph and the hypoplactic analogue
of the Robinson–Schensted–Knuth correspondence exactly parallels the
very elegant interaction of the crystal graph and the usual Robinson–
Schensted–Knuth correspondence. Just as the connected components
of the crystal graph Γ(placn ) are indexed by standard Young tableaux,
the connected components of the quasi-crystal graph Γ(hypon ) are indexed by recording ribbons:
Theorem 7.1. Let u, v ∈ A∗n . The words u and v lie in the same
connected component of Γ(hypon ) if and only if RR(u) = RR(v).
Proof. Suppose that u and v lie in the same connected component of
Γ(hypon ). Note first that |u| = |v|. Let u = u1 · · · uk and v = v1 · · · vk ,
where uh , vh ∈ An . By Proposition 6.1, std(u) = std(v). Therefore
std(u1 · · · uh ) = std(v1 · · · vh ) for all h (this is immediate from the definition of standardization [Nov00, Lemma 2.2]). Thus QR(u1 · · · uh )
and QR(v1 · · · vh ) both have shape DC(std(u1 · · · uh )−1 ) for all h. The
sequence of these shapes determines where new symbols are inserted

34

ALAN J. CAIN AND ANTÓNIO MALHEIRO

during the computation of QR(u) and QR(v) by Algorithm 4.3, and so
RR(u) = RR(v).
Now suppose RR(u) = RR(v). Let û and v̂ be the highest-weight
words in Γ(hypon , u) and Γ(hypon , v), respectively. By the forward
implications, RR(û) = RR(u) = RR(v) = RR(v̂). Note that û ∼
C(QR(û)) and v̂ ∼ C(QR(v̂)), and C(QR(û)) and C(QR(v̂)) are highestweight quasi-ribbon words. Furthermore, the quasi-ribbon tableaux
QR(û) and QR(v̂) have the same shape, since they both have the
same shape as RR(û) = RR(v̂). By Corollary 6.5, wt(C(QR(û))) =
wt(C(QR(v̂))); thus C(QR(û)) = C(QR(û)) by Corollary 6.6. Since
QR(û) = QR(û) and RR(û) = RR(v̂), it follows that û = v̂ by the
quasi-ribbon tableau version of the Robinson–Schensted–Knuth correspondence (see the discussion in Section 4). Hence Γ(hypon , u) =
Γ(hypon , û) = Γ(hypon , v̂) = Γ(hypon , v). This completes the proof of
the reverse implication.

8. Structure of the quasi-crystal graph
The aim of this section is to study the structure of quasi-crystal graph
and how it interacts with usual crystal graph. Many of these results
are illustrated in the components of Γ(hypo4 ) and Γ(plac4 ) shown in
Figures 5 to 8. These figures show both the actions of quasi-Kashiwara
operators (indicated by solid lines) and other actions of Kashiwara
operators (indicated by dotted lines). (Recall from Proposition 5.2
that the action of the quasi-Kashiwara operators is a restriction of the
action of the Kashiwara operators.)
8.1. Sizes of classes and quasi-crystals. As previously noted, by
fixing a Young tableau P and varying Q over all standard Young
tableaux of the same shape as P , one obtains the plactic class corresponding to P . Notice that one obtains as a corollary that the size of
this class depends on the shape of P , not on the entries of P . The
so-called hook-length formula gives the number of standard Young
tableaux of a given shape (see [FRT54] and [Ful97, § 4.3]) and thus
of the size of a plactic class corresponding to an element of that shape.
This section uses the quasi-crystal graph to give an analogue of the
hook-length formula for quasi-ribbon tableaux, in the sense of stating
a formula for the size of hypoplactic classes corresponding to quasiribbon tableau of a given shape. Novelli [Nov00, Theorem 5.1] proves
that for any compositions α = (α1 , . . . , αh ) and γ,


X
α1 + . . . + αh
(8.1)
#(β, γ) =
,
α
1 , . . . , αh
βα
where #(β, γ) is the size of the hypoplactic class corresponding to the
quasi-ribbon tableau of shape β and content γ. (Recall that β  α
denotes that β is a coarser composition than α; see Section 4.) Since

CRYSTALLIZING THE HYPOPLACTIC MONOID
1111

Legend

1112

QuasiKashiwara
operators

1122 1113
1222 1123 1114

z}|{
1
2
3

2222 1223 1133 1124
2223 1233 1224 1134
2233 1333 1234 2224 1144

35

4321

2333 2234 1334 1244
3333 2334 2244 1344
3334 2344 1444
3344 2444
3444
4444

Figure 5. The connected components Γ(hypo4 , 1111)
and Γ(hypo4 , 4321) of the quasi-crystal graph Γ(hypo4 ).
These are also the connected components Γ(plac4 , 1111)
and Γ(plac4 , 4321) of the crystal graph Γ(plac4 ): there
is no vertex in these components where some ẽi or f˜i is
defined but the corresponding ëi or f¨i is not. These two
components are not isomorphic to any other components
of either Γ(hypo4 ) or Γ(plac4 ). The other components of
Γ(hypon ) and Γ(placn ) whose vertices are length-4 words
are shown in Figures 6 and 7.
the size of the hypoplactic class corresponding to a quasi-ribbon tableau
of shape (α1 ) is always 1, the formula (8.1) allows one to iteratively
compute the size of an arbitrary hypoplactic class.
However, it is not immediately clear from (8.1) that the size of a
hypoplactic class is only dependent on the shape of the quasi-ribbon
tableau, not on its content:
Proposition 8.1. Hypoplactic classes corresponding to quasi-ribbon
tableaux of the same shape all have the same size.
Proof. Let u, v ∈ A∗n be such that QR(u) and QR(v) have the same
shape. Then C(QR(u)) and C(QR(v)) lie in the same connected component by Proposition 6.4(1). Thus there is a sequence g̈i1 , . . . , g̈ir
of operators ëi and f¨i such that g̈i1 · · · g̈ir (C(QR(u))) = C(QR(v)).
¨
Each
is a bijection
between ≡hypo -classes, and
 ëi and fi, when defined,


so C(QR(u)) ≡hypo and C(QR(v)) ≡hypo have the same size. Since
u ∼ C(QR(u)) and v ∼ C(QR(v)), it follows that [u]≡hypo and [v]≡hypo
have the same size.


36

ALAN J. CAIN AND ANTÓNIO MALHEIRO
2111

to Γ(hypo4 , 3212)
(See Fig. ??)

3111

2112

3112 4111

2113

2122

2131

3122 4112

3113 2114

2123

3131 2141

2132

2133 2124

3132 3141

2142

3222 4122 4113 3123 3114

2121

4222 4123

3223 3124 4114 3133 2134

3232 3142 4141 2143

4223 4133

3224 4124

3233 3134 2144

3242 4142

3143

4233

4224 4134

3234 3144

4242 4143

3243

4333

4234

3244 4144

4243

4334

4244

4343

1211

4344

1311

1212

1312 1411

1213

2212

2311

1322 1412

1313 1214

2213

3311 2411

2312

2313 2214

3312 3411

2412

2322 1422 1413 1323 1314

2211

2422 1423

2323 1324 1414 3313 2314

3322 3412 4411 2413

2423 1433

2324 1424

3323 3314 2414

3422 4412

3413

2433

2424 1434

3324 3414

4422 4413

3423

3433

2434

3424 4414

4423

3434

4424

4433

1121

4434

1131

1221

1132 1141

1231

2221

1232 1142

1331 1241

2231

2232 1242 1143 1332 1341

2331 2241

2242 1243

2332 1342 1441 3331 2341

2243 1343

2342 1442

3332 3341 2441

2343

2442 1443

3342 3441

3343

2443

3442 4441

3443

4442

Legend
QuasiKashiwara
operators

z}|{
1
2
3

Kashiwara
operators

z}|{
1
2
3

4443

Figure 6. Thirteen components of Γ(hypo4 ), which together lie inside five components of Γ(placn ). Dotted
lines show actions of operators ẽi and f˜i that are not also
actions of operators ëi and f¨i . Each of these components
of Γ(hypo4 ) is isomorphic to at least one other component; grey lines link isomorphic components. Other components are shown in Figures 5 and 7.

CRYSTALLIZING THE HYPOPLACTIC MONOID
to Γ(hypo4 , 2132)
(See Fig. ??)

Legend

4211

3212

4311

4212

3213

QuasiKashiwara
operators

4312

4213

3214

4322

4313

4214

4323

4314

3211

3121

4324

4121

3221

4131

4221

3231

4132

4231

3241

4232

4331

4241

4332

4341

1321

37

z}|{
1
2
3

Kashiwara
operators

z}|{
1
2
3

4342

1421

2321

1431

2421

3321

1432

2431

3421

2432

3431

4421

3432

4431
4432

Figure 7. Nine components of Γ(hypo4 ), which together lie inside three of the connected components
Γ(placn ). Dotted lines show actions of operators ẽi and
f˜i that are not also actions of operators ëi and f¨i . Each
of these components of Γ(hypo4 ) is isomorphic to at least
one other component; grey lines link isomorphic components. The other components whose vertices are length-4
words are shown in Figures 5 and 6.

The formula for the size of hypoplactic classes is also straightforward
when one uses the quasi-crystal graph:
Theorem 8.2. The size of any hypoplactic class in A∗n whose quasiribbon tableau has shape α is

(8.2)

X


 (−1)`(α)−`(β)



βα

0

|β|
β1 , · · · , β`(β)



if `(α) ≤ n,
otherwise.

38

ALAN J. CAIN AND ANTÓNIO MALHEIRO

Proof. Note first that in a quasi-ribbon tableau, any symbol in An
must lie in the first n rows. Thus if `(α) > n, then there is no quasiribbon tableau of shape α with entries in An and so the corresponding
hypoplactic class if empty. So assume henceforth that `(α) ≤ n.
Let T be a quasi-ribbon tableau of shape α; the aim is to describe
the cardinality of the set UT = { u ∈ A∗n : QR(u) = T }. Since the
operators ëi and f¨i are bijections between hypoplactic classes, assume
without loss of generality that C(T ) is highest-weight. By Corollary 6.5,
wt(C(T )) = α. Since all words in a hypoplactic class have the same
weight, every word in UT has weight α (and thus contains exactly αi
symbols i, for each i ∈ An ). Furthermore, all words in UT are highestweight and so have i-inversions for each i ∈ {1, . . . , `(α)}. Thus UT
consists of exactly the words of weight α, but that do not have the
property of containing all symbols i to the left of all symbols i + 1 for
some i ∈ {1, . . . , `(α) − 1}.
For any weak composition γ with `(γ) ≤ n, the number of words in
A∗n with weight γ is


|γ|
.
γ1 , · · · , γ`(γ)
Consider a word u ∈ A∗n with wt(u) = γ that is i-inversion-free. Then
in u, every symbol i lies to the left of every symbol i + 1. Replacing
each symbol j + 1 by j for each j ≥ i yields a word u0 with weight
γ 0 = (γ1 , . . . , γi−1 , γi + γi+1 , γi+2 . . . , γn ); note that γ 0  γ and `(γ 0 ) =
`(γ)−1. On the other hand, starting from u0 and replacing each symbol
j by j + 1 for j ≥ i + 1 and replacing the rightmost γi+1 symbols i by
i+1 yields u. Thus there is a one-to-one correspondence between words
of weight γ that are i-inversion-free and words of weight γ 0 .
Iterating this argument shows that there is a one-to-one correspondence between words of weight γ that are i-inversion-free for i ∈ I ⊆
{1, . . . , n − 1} and words of weight γI for a (uniquely determined)
γI  γ.
Hence, by the inclusion–exclusion principle, the number of such words
that are i-inversion-free for all i ∈ {1, . . . , n − 1} is given by (8.2). 
For example, let α = (2, 1, 1, 2). By Theorem 8.2, the size of the
hypoplactic class whose quasi-ribbon tableau has shape α is
6!
6!
6!
6!
−
−
−
2!1!1!2! 3!1!2! 2!2!2! 2!1!3!
6!
6!
6!
+
+
+
4!2! 3!3! 2!4!
6!
− = 19.
6!

CRYSTALLIZING THE HYPOPLACTIC MONOID

39

The quasi-ribbon word 143214 corresponds to a quasi-ribbon tableau
with shape α, and the hypoplactic class containing u is
{143214, 413214, 431214, 432114,
143241, 413241, 431241, 432141,
143421, 413421, 431421, 432411,
144321, 414321, 434121, 434211,
441321, 443121, 443211},
which contains 19 elements, as expected.
For the sake of completeness, this section closes with a formula for
the number of quasi-ribbon tableaux of a given shape, which allows one
to compute the size of a connected component of Γ(hypon ). Notice that
the proof of this does not depend on applying the crystal structure.
Theorem 8.3. The number of quasi-ribbon tableaux of shape α and
symbols from An is
(

n+|α|−`(α)
n−`(α)

0



if `(α) ≤ n
if `(α) > n.

Proof. Consider a ribbon diagram of shape α, where the boundaries
between the cells, including the left boundary of the first cell and the
right boundary of the last cell, are indexed by the numbers 0, 1, . . . , |α|.
Notice that D(α) be the set of indices of boundaries between vertically
adjacent cells. For example, for shape α = (4, 4, 2, 3), the indices are
as follows:
0

1

2

3
6

7
9

4
5

12 13

8
10
11

In this case, D(α) = {4, 8, 10}.
A filling of such a quasi-ribbon tableau by symbols from An is weakly
increasing from upper left to lower right, and is specified exactly by
listing n − 1 boundaries between adjacent cells where the increase from
i to i + 1 occurs in this filling. Note that such a list may contain
repeated entries (and is thus formally a multiset), indicating that the
difference between the entries in the cells incident on this boundary

40

ALAN J. CAIN AND ANTÓNIO MALHEIRO

differ by more than 1. For example, for n = 9 the filling
0

1

2

3

2 4 4 4 6 7
4 5 5 6 7 9
12 13
5
8 8 8
10 9 9 9
11

corresponds to the multiset
h0, 1, 1, 4, 6, 7, 8, 10i.
Note that this multiset has length n − 1 = 8 and contains the entry
0, indicating the presence of 2 in the first cell, and a repeated entry
1, indicating the jump from 2 to 4 at this boundary. However, some
of the entries in this multiset are forced by the shape of the tableau:
there must be increases at boundaries 4, 8, and 10, which are between
vertically adjacent cells.
There is thus a one-to-one correspondence between multisets with
n − 1 elements drawn from {0, . . . , |α|} and that contain D(α) (which
indicates the position of the ‘forced’ increases) and fillings of a tableau
of shape α. Since |D(α)| = `(α)−1, the number of such multisets is 0 if
`(α) > n, and is otherwise the number of multisets with (n−1)−(`(α)−
1) elements drawn from {0, . . . , |α|}, which is (|α|+1)+((n−1)−(`(α)−1))−1
(n−1)−(`(α)−1)
by the standard formula forthe number of multisets [Sta12, § 1.2],
which simplifies to n+|α|−`(α)
.

n−`(α)
8.2. Interaction of the crystal and quasi-crystal graphs. This
section examines the interactions of the crystal graph Γ(placn ) and
quasi-crystal graph Γ(hypon ). The first, and most fundamental, observation, is how connected components in Γ(placn ) are made up of
connected components in Γ(hypon ):

Proposition 8.4. The vertex set of every connected component of
Γ(placn ) is a union of vertex sets of connected components of Γ(hypon ).
Proof. By Proposition 5.2, any edge in Γ(hypon ) (whose edges indicate
the action of the quasi-Kashiwara operators ëi and f¨i ) is also an edge
in Γ(placn ) (whose edges indicate the action of the Kashiwara operators ẽi and f˜i ). Hence every connected component in Γ(hypon ) lies
entirely within a connected component of Γ(placn ); the result follows
immediately.

For example, as shown in Figure 6, the connected component Γ(plac4 , 2111)
is made up of the three connected components Γ(hypo4 , 2111), Γ(hypo4 , 2112),
and Γ(hypo4 , 2122).

CRYSTALLIZING THE HYPOPLACTIC MONOID

41

Proposition 8.5. Let Θ : Γ(placn , u) → Γ(placn , Θ(u)) be a crystal
isomorphism. Then Θ restricts to a quasi-crystal isomorphism from
Γ(hypon , w) to Γ(hypon , Θ(w)), for all w ∈ Γ(placn , u).
Proof. Let Θ : Γ(placn , u) → Γ(placn , Θ(u)) be a crystal isomorphism
and let w ∈ Γ(placn , u). Suppose the Kashiwara operator f˜i is defined
on w but the quasi-Kashiwara operator f¨i is not defined on w. Since f˜i
is defined, w must contain at least one symbol i. Thus, since f¨i is undefined, w must have an i-inversion. Since Θ is a crystal isomorphism,
w ≡plac Θ(w). The defining relations in Rplac preserve the property of
having i-inversions (for if a defining relation in Rplac commutes a symbol i and i + 1, then a = i and c = i + 1 in this defining relation, and
so b ∈ {i, i + 1}, and so the applied relation is either (i(i + 1)i, (i + 1)ii)
or ((i + 1)i(i + 1), (i + 1)(i + 1)i), and both sides of these relations have
i-inversions). Hence Θ(w) has an i-inversion. Hence f¨i is not defined
on w.
A symmetric argument shows that if f˜i is defined on Θ(w) but
f¨i is not, then f¨i is not defined on w. Hence the isomorphism Θ
maps edges corresponding to actions of quasi-Kashiwara operators in
Γ(placn , u) to edges corresponding to actions of quasi-Kashiwara operators in Γ(placn , Θ(u)), and vice versa, and so restricts to a quasicrystal isomorphism from Γ(hypon , w) to Γ(hypon , Θ(w)) for all w ∈
Γ(placn , u).

Notice that it is possible for a single connected component of Γ(placn )
to contain distinct isomorphic connected components of Γ(hypon ). For
example, as shown in Figure 8, the connected component Γ(plac4 , 321211)
contains the isomorphic connected components Γ(hypo4 , 321213) and
Γ(hypo4 , 321312).
Note also that Γ(plac4 , 321211), contains the isomorphic one-vertex
connected components Γ(hypo4 , 421323) and Γ(hypo4 , 321423). (There
are other one-vertex components of Γ(hypo4 ) inside Γ(plac4 , 321211),
but these have different weights and so there are no quasi-crystal isomorphisms between them.) The quasi-ribbon tableau QR(421323) has
shape (1, 2, 2, 1); thus, by Theorem 8.2, the hypoplactic class containing
421323 has size
6!
6!
6!
6!
−
−
−
1!2!2!1! 3!2!1! 1!4!1! 1!2!3!
6!
6!
6!
+
+
+
5!1! 3!3! 1!5!
6!
− = 61.
6!
Since there are an odd number of components that are isomorphic to
Γ(hypo4 , 421323), it follows that there must be at least one component of Γ(plac4 ) that contains an odd number of these components.

42

ALAN J. CAIN AND ANTÓNIO MALHEIRO

321211
Legend

421211

321311 321212

421311

321411 421212 321312 321213

QuasiKashiwara
operators

431311 421312 421411 421213 321412 321214 321322 321313
431312 421322 431411 421313 421412 421214 321422 321314 321413 321323

z}|{
1
2
3

431322 421323 431412 431313 421413 421314 421422 321414 321423 321324 Kashiwara
operators
432322 421324 431422 431323 431413 431314 421423 421414 321433 321424
z}|{
432422 432323 431423 431324 421433 431414 321434 421424
432423 432324 431433 431424

421434

432433 432424

431434

1
2
3

432434

Figure 8. The connected component Γ(plac4 , 321211),
drawn so that the connected components of Γ(hypo4 )
are arranged vertically. Notice that it contains the
isomorphic connected components Γ(hypo4 , 321213) and
Γ(hypo4 , 321312), and also the isomorphic one-vertex
connected
components
Γ(hypo4 , 421323)
and
Γ(hypo4 , 321423).
Thus different components of Γ(plac4 ) may contain different numbers
of isomorphic components of Γ(hypo4 ).
Corollary 8.6. Let u, v ∈ A∗n be such that u ≡plac v but u 6= v,
so that there is a non-trivial crystal isormorphism Θ : Γ(placn , u) →
Γ(placn , v) with Θ(u) = v. Let s ∈ Γ(placn , u) and t ∈ Γ(placn , v) be
quasi-ribbon words. Then Θ does not map Γ(hypon , s) to Γ(hypon , t).
More succinctly, quasi-ribbon word components of Γ(hypon ) cannot lie
in the same places in distinct isomorphic components of Γ(placn ).
Proof. Without loss of generality, assume s and t are highest-weight
in Γ(hypon , s) and Γ(hypon , t) respectively. Suppose, with the aim
of obtaining a contradiction, that Θ maps Γ(hypon , s) to Γ(hypon , t).
Then Θ(s) = t, and so s ≡hypo t. Since s and t are quasi-ribbon words,
s = t by Proposition 6.4 and so Θ is trivial, which is a contradiction.

Corollary 6.2 showed that the quasi-Kashiwara operators preserve
shapes of quasi-ribbon tableau. In fact, quasi-Kashiwara operators and,
more generally, Kashiwara operators, preseve shapes of quasi-ribbon
tabloids (see Section 4 for the definitions of quasi-ribbon tabloids):

CRYSTALLIZING THE HYPOPLACTIC MONOID

43

Proposition 8.7. Let i ∈ {1, . . . , n − 1}. Let u ∈ A∗n .
(1) If the Kashiwara operator ẽi is defined on u, then QRoid(ẽi (u))
and QRoid(u) have the same shape.
(2) If the Kashiwara operator f˜i is defined on u, then QRoid(f˜i (u))
and QRoid(u) have the same shape.
Proof. Let u ∈ A∗n and let u = u(1) · · · u(m) be the factorization of u
into maximal decreasing factors (which are entries of the columns of
QRoid(u)).
Suppose that the Kashiwara operator ẽi is defined on u, and that the
application of ẽi to u replaces the (necessarily unique) symbol i + 1 in
u(k) by a symbol i; let û(k) be the result of this replacement. Then u(k)
cannot contain a symbol i, for if it did, then during the computation of
the action of ẽi as described in Subsection 3.3, the symbols i + 1 and i
in u(k) (which would be adjacent since u(k) is strictly decreasing) would
have been replaced by − and + and so would have been deleted, and
so ẽi would not act on this symbol i + 1. Hence û(k) is also a decreasing
word.
Furthermore, the first symbol of u(k+1) is greater than or equal to
the last symbol of u(k) , and so is certainly greater than or equal to the
last symbol of û(k) since ẽi can only decrease a symbol.
Similarly, the first symbol of u(k) is greater than or equal to the last
symbol of u(k−1) . If u(k) does not start with the symbol i + 1, the first
symbol of û(k) is greater than or equal to the last symbol of u(k−1) .
So assume u(k) starts with the symbol i + 1; since the factorization is
into maximal decreasing factors, u(k−1) ends with a symbol that is less
than or equal to i + 1. If u(k−1) ends with a symbol that is strictly
less than i + 1, then the first symbol of û(k) is greater than or equal
to the last symbol of u(k−1) . So assume u(k−1) ends with the symbol
i + 1. Then during the computation of the action of ẽi as described in
Subsection 3.3, the adjacent symbols i + 1 at the end of u(k−1) and at
the start of u(k) are both replaced by symbols −, and neither of these
symbols are removed by deletion of factors −+, since ẽi acts on the
symbol i + 1 at the start of u(k) . But this contradicts the fact that ẽi
acts on the symbol replaced by the leftmost −. Thus this case cannot
arise, and so one of the previous possibilities must have held true.
Combining the last three paragraphs shows that the factorization of
ẽi (u) into maximal decreasing factors is ẽi (u) = u(1) · · · u(k−1) û(k) u(k+1) · · · u(m) .
This proves part (1). Similar reasoning for f˜i proves part (2).

Proposition 8.8. A connected component of Γ(placn ) contains at most
one quasi-ribbon word component of Γ(hypon ).
Proof. Suppose the connected component Γ(placn , u) contains connected
components Γ(hypon , w) and Γ(hypon , w0 ) that both consist of quasiribbon words. Without loss of generality, assume that w is highest-

44

ALAN J. CAIN AND ANTÓNIO MALHEIRO
1
21
2

2
1
21
3

2
1
31
3

1

1
21
4

3

1
32
3

1

3

3
2
42
4

2
2
43
4

2
1

2
1
31
4

3

2
32
3
2
32
4

1

3

1

3

1
32
4

1

1

1

3
1
42
4

3
1
22
4

2
1
41
4

1

1
22
3

1
23
4

2
1
33
4

3
1
2 2

2
1
43
4

33
4

3

2
3
43
4

Figure 9. The component Γ(plac4 , 2121), with words
drawn as quasi-ribbon tabloids of the same shape. Only
the component Γ(hypo4 , 2132) consists of quasi-ribbon
words, which thus appear here as quasi-ribbon tableaux.
weight in Γ(hypon , w) and w0 has highest-weight in Γ(hypon , w0 ). Since
w and w0 are in the connected component Γ(placn , u), the quasi-ribbon
tableaux QR(w) and QR(w0 ) have the same shape by Proposition 8.7.
Hence by Corollary 6.5, wt(w) = wt(w0 ) and so w = w0 by Corollary 6.6. Thus Γ(hypon , w) = Γ(hypon , w0 ).

It is possible that a connected component of Γ(placn ) contains no
quasi-ribbon word components of Γ(hypon ). For example, as can be
seen in Figure 6, Γ(plac4 , 2211) contains the connected components
Γ(hypo4 , 2211) and Γ(hypo4 , 2312), and neither 2211 nor 2312 is a
quasi-ribbon word. Thus the next aim is to characterize those connected components of Γ(placn ) that contain a (necessarily unique)
quasi-ribbon word component of Γ(hypon ). In order to do this, it

CRYSTALLIZING THE HYPOPLACTIC MONOID

45

is useful to discuss a shortcut that allows one to calculate quickly the
Young tableau P(w) obtained when w is a quasi-ribbon word.
The slide up–slide left algorithm takes a filled quasi-ribbon diagram
D and produces a filled Young diagram as follows: Start from the quasiribbon diagram D. Slide all the columns upwards until the topmost
entry of each is on row 1. Now slide all the symbols leftwards along
their rows until the leftmost entry in each row is in the first column
and there are no gaps in each row.
As will be shown in Proposition 8.9(1), applying the slide up–slide
left algorithm to a quasi-ribbon tableau QR(u) gives the Young tableau
P(u), as in the following example:
QR(1325436768) = 1 2
3 3
4
5 6 6
7 8
1 2
3
3
4 6 6
8
5
7
1 2 3 6 6 8
3 4
7
5
1 2 3 6 6 8
3 4
7
5
1 2 3 6 6 8 = P(1325436768).
3 4 7
5

Similarly, as will be shown in Proposition 8.9(2), applying the slide
up–slide left algorithm to a quasi-ribbon tableau of the same shape
α as QR(u), filled with entries 1, . . . , `(α), gives the standard Young
tableau Q(u), as in the following example:
1 2
3 4
5
6 7 8
9 10

1 2 4 7 8 10 = Q(1325436768).
3 5 9
6

Proposition 8.9. Let T be a quasi-ribbon tableau of shape α.
(1) Applying the slide up–slide left algorithm to T yields the Young
tableau P(C(T )).

46

ALAN J. CAIN AND ANTÓNIO MALHEIRO

(2) Applying the slide up–slide left algorithm to the (unique) quasiribbon tableau of shape α filled with entries 1, . . . , |α| yields the
standard Young tableau Q(C(T )).
Proof. Let U be the unique quasi-ribbon tableau of shape α filled with
entries 1, . . . , |α|. The proof is by induction on the number of columns
m in a ribbon diagram of shape α.
Suppose m = 1. Then applying the slide up–slide left algorithm to T
and U yields T and U , respectively (viewed as filled Young diagrams).
Since T satisifies the condition for being a Young tableau, P(C(T )) =
T . Furthermore, U is also the unique standard Young tableau with a
single column of the same shape as T , and so must be Q(C(T )).
Now suppose m > 1 and that the result holds for all quasi-ribbon
tableau T 0 with fewer than m columns. In particular, it holds for
the quasi-ribbon tableau T 0 formed by the first m − 1 columns of T .
In particular, by applying the slide up–slide left algorithm to T 0 , one
obtains P(C(T 0 )). If the m-th column of T contains entries a1 , . . . , ak
(listed from bottom to top, so that a1 > . . . > ak ), then applying
the slide up–slide left algorithm to T yields the filled Young diagram
obtained by applying it to T 0 (which yields P(C(T 0 ))) and then adding
the symbol ah at the rightmost end of the h-th row. Since each symbol
a1 , . . . , ak is greater or equal to than every symbol in T 0 and thus in
P(C(T 0 )), using Algorithm 4.2 to insert the symbols a1 , . . . , ak into
P(C(T 0 )) does not involve bumping any symbols in P(C(T 0 )). That
is, the symbols a1 , . . . , ak (which form a strictly decreasing sequence)
bump each other up the rightmost edge of P(C(T 0 )), as in the following
example
0

P(C(T ))

a2
a1

a 3 ← a4 =

0

P(C(T ))

a4
a3
a2

a1

Furthermore, applying the slide up–slide left algorithm to the unique
quasi-ribbon tableau of the same shape as T 0 filled with entries 1, . . . , (|α|−
k) yields the standard Young tableau Q(C(T 0 )). Thus applying the
slide up–slide left algorithm to the unique quasi-ribbon tableau of shape
α filled with entries 1, . . . , |α| yields the filled Young diagram obtained
by applying it to Q(C(T 0 )) and adding |α| − k + h to the end of the
h-th row for h = 1, . . . , k. By the above analysis of the behaviour of
Algorithm 4.2, this is the standard Young tableau Q(C(T )).

Proposition 8.10. Let Q be a standard Young tableau. There is at
most one quasi-ribbon tableau T such that Q can be obtained by applying
the slide up–slide left algorithm to T .
Proof. Suppose that T and T 0 are quasi-ribbon tableaux such that applying the slide up–slide left algorithm to T and T 0 yields Q. Then

CRYSTALLIZING THE HYPOPLACTIC MONOID

47

by Proposition 8.9(1–2), P(C(T )) = Q(C(T )) = Q = P(C(T 0 )) =
Q(C(T 0 )). Thus by the Robinson–Schensted–Knuth correspondence,
C(T ) = C(T 0 ) and so T = T 0 .

Proposition 8.11. A connected component Γ(placn , w) contains a quasiribbon word component if and only if Q(w) can be obtained by applying
the slide up–slide left algorithm to some quasi-ribbon tableau T of shape
α and entries 1, . . . , |α| and such that `(α) ≤ n.
Proof. Suppose Γ(placn , w) contains a quasi-ribbon word component.
Let u ∈ Γ(placn , w) be a quasi-ribbon word. Let α be the shape of
QR(u). Note that QR(u) has at most n rows, so `(α) ≤ n. By Proposition 8.9(2), applying the slide up–slide left algorithm to the unique
quasi-ribbon tableau of shape α filled with entries 1, . . . , |α| yields the
standard Young tableau Q(u). Since u and w are in the same connected
component of Γ(placn ), the standard Young tableaux Q(w) and Q(u)
are equal.
On the other hand, suppose that Q(w) can be obtained by applying
the slide up–slide left algorithm to some quasi-ribbon tableau T of
shape α and entries 1, . . . , |α| and such that `(α) ≤ n. Let U be the
quasi-ribbon tableau of shape α and entries in An such that C(U ) is
highest-weight in its component of Γ(hypon ); note that U exists since
`(α) ≤ n. Then by Proposition 8.9(2), Q(C(U )) = Q(w) since U has
shape α. Hence C(U ) ∈ Γ(placn , w).

Define a permutation σ of {1, . . . , n} to be interval-reversing if there
is some composition α = (α1 , . . . , αk ) with |α| = n such that for all
h = 0, . . . , k, the permutation σ preserves the interval {α1 + . . . + αh +
1, . . . , α1 + . . . + αh+1 } and reverses the order of its elements. (For
h = 0, this interval is {1, . . . , α1 }.) Thus, for example,


1 2 3 4 5 6 7 8
1 5 4 3 2 8 7 6
is an interval-reversing permutation of {1, . . . , 8}, where the appropriate composition α is (1, 4, 3). It is clear that there is only one choice
for α.
It is well-known that if w is a standard word (and thus a permutation), then the Robinson–Schensted–Knuth correspondence associates w with (P(w), Q(w)) and w−1 with (Q(w), P(w)). That is,
Q(w) = P(w−1 ) and P(w) = Q(w−1 ). Thus involutions are associated
to pairs (Q, Q), where Q is a standard Young tableau.
Proposition 8.12. A connected component Γ(placn , w) contains a quasiribbon word component if and only if the Robinson–Schensted–Knuth
correspondence associates (Q(w), Q(w)) with an interval-reversing involution.

48

ALAN J. CAIN AND ANTÓNIO MALHEIRO

Proof. Suppose Γ(placn , w) contains a quasi-ribbon word. By Proposition 8.11, Q(w) can be obtained by applying the slide up–slide left algorithm to some quasi-ribbon tableau T of shape β and entries 1, . . . , |β|
and such that `(β) ≤ n. By Proposition 8.9(1–2), P(C(T )) = Q(C(T )) =
Q(w). So the Robinson–Schensted–Knuth correspondence associates
(Q(w), Q(w)) wih C(T ). Let α = (α1 , . . . , αk ) be such that αi is the
length of the i-th column of T . Then by the definition of T and its
column reading, C(T ) is an interval-reversing permutation where the
appropriate composition is α.
On the other hand, suppose the Robinson–Schensted–Knuth correspondence associates (Q(w), Q(w)) with an interval-reversing involution u, where the appropriate composition is α = (α1 , . . . , αk ). Note
that Q(w) = P(u) and Q(w) = Q(u). Let T be the quasi-ribbon tabloid
QRoid(u). Then αi is the length of the i-th column of T , which is filled
with the image of the interval {α1 + . . . + αi + 1, . . . , α1 + . . . + αi+1 }
since u is an interval-reversing permutation. Since the elements in
each interval are less than the elements in the next, the rows of T
are increasing from left to right and so T is a quasi-ribbon tableau
that is filled with the symbols 1, . . . , |u|. Note that u = C(T ), and
so Q(w) = Q(u) = Q(C(T )). So by Proposition 8.9, Q(w) can be
obtained from T by applying the slide up–slide left algorithm. Hence
Γ(placn , w) contains a quasi-ribbon word by Proposition 8.11.

Corollary 8.13. Let w ∈ A∗n and let λ = (λ1 , . . . , λ`(λ) ) be the shape
of P(w). The number of connected components of Γ(placn ) that are
isomorphic to Γ(placn , w) and contain quasi-ribbon word components
of Γ(hypon ) is


λ1

if |λ| − λ1 + 1 ≤ n,
λ1 − λ2 , . . . , λ`(λ)−1 − λ`(λ) , λ`(λ)

0
otherwise.

Proof. By Proposition 8.11, the number of such components is equal
to the number of standard Young tableaux of shape λ that can be
obtained by applying the slide up–slide left algorithm to some quasiribbon tableau of some shape α and entries 1, . . . , |α| and such that
`(α) ≤ n. By the definition of a quasi-ribbon diagram, the number
of rows `(α) of such a diagram is equal to the total number of boxes
minus the number of columns plus 1 (since adjacent pairs of columns
overlap in exactly one row). Since the slide up–slide left algorithm
preserves the number of columns and the total number of boxes, this
number of rows is |λ| − λ1 + 1. Hence if |λ| − λ1 + 1 > n, there is
no standard Young tableau that can be obtained in such a way. So
suppose henceforth that |λ| − λ1 + 1 ≤ n.
For any composition α, there is exactly one quasi-ribbon tableau of
shape α filled with symbols 1, . . . , |α|, and each of them yields (under
the slide up–slide left algorithm) a different standard Young tableau by

CRYSTALLIZING THE HYPOPLACTIC MONOID

49

Proposition 8.11. Furthermore, there is a one-to-one correspondence
between compositions α and shapes of tabloids: one simply takes a
ribbon diagram of shape α and applies the ‘slide up’ part of the slide
up–slide left algorithm. Thus, to obtain the number of such quasiribbon tableaux that give the correct shape on applying the slide up–
slide left algorithm, it suffices to count the number of tabloid shapes
that have λj cells on the j-th row, for each j = 1, . . . , `(λ). This is
equal to the number of tabloid shapes that have λ1 cells on the first
row and λj − λj+1 columns ending on the j-th row, which in turn is
equal to the number of words of length λ1 containing λj − λj+1 symbols
j for each j < `(λ) and λ`(λ) symbols `(λ).

Note that the number of components specified by Corollary 8.13
is dependent only on the shape of P(w), not on wt(w) or w itself.
This is what one would expect in working with a class of isomorphic
components in Γ(placn ).
Corollary 8.14. Let w ∈ A∗n , and let λ = (λ1 , . . . , λm ) be the shape of
P(w). Suppose |λ| − λ1 + 1 ≤ n. Then Γ(placn , w) contains at least


λ1
λ1 − λ2 , . . . , λ`(λ)−1 − λ`(λ) , λ`(λ)
connected components of Γ(hypon ).

Proof. Corollary 8.13 gives the number of components isomorphic to
Γ(placn , w) that contain quasi-ribbon word components. Each one of
these quasi-ribbon word components is isomorphic to a connected component of Γ(hypon ) inside Γ(placn , w) by Proposition 8.5, and to distinct such connected components of Γ(hypon ) by Corollary 8.6. Hence
the number of connected components of Γ(hypon ) inside Γ(placn , w)
must be at least the number given in Corollary 8.13 in the case where
|λ| − λ1 + 1 ≤ n.

8.3. The Schützenberger involution. The Schützenberger involution is the map ] : A∗n → A∗n that sends a ∈ An to n − a + 1 and
is extended to A∗n by (a1 · · · ak )] 7→ ak ] · · · a1 ] . That is, given a word,
one obtains its image under ] by reversing the word and replacing each
symbol a by n − a + 1. It is well-known that the Schützenberger involution reverses the order of weights, in the sense that if u has higher
weight than v, then v ] has higher weight than u] .
Proposition 8.15. In Γ(hypon ), the Schützenberger involution maps
connected components to connected components. If there is an edge
from u to v labelled by i, then there is an edge from v ] to u] labelled by
n − i.
Proof. Clearly the second statement implies the first. So suppose that
f¨i (u) = v. Then u contains at least one symbol i and, every symbol i is

50

ALAN J. CAIN AND ANTÓNIO MALHEIRO

to the left of every symbol i + 1, and v is obtained from u by replacing
the rightmost symbol i by i + 1. By the definition of ] , in the word u] ,
every symbol n − i + 1 is to the right of every symbol n − i. Hence
ën−i (u] ) is defined, is equal to the word obtained from u] by replacing
the leftmost symbol n − i + 1 by n − i, which is v ] . Hence there is an
edge from v ] to u] labelled by n − i.

8.4. Characterizing quasi-crystal graphs? Stembridge [Ste03] gives
a set of axioms that characterize connected components of crystal
graphs. These axioms specify ‘local’ conditions that the graph must
satisfy. It is natural to ask whether there is an analogous characterization for quasi-crystal graphs:
Question 8.16. Is there a local characterization of quasi-crystal graphs?
However, the Stembridge axioms are connected with the underlying
representation theory, in the sense that they refer to whether the arrow labels correspond to orthogonal roots of the algebra. Since the
quasi-crystal graphs are defined on a purely combinatorial level, any
characterization of them must also be on a purely combinatorial level.
9. Applications
9.1. Counting factorizations. One interpretation of the Littlewood–
Richardson rule [Ful97, ch. 5] is that the Littlewood–Richardson coefficients cνλµ give the number of different factorizations of an element
of plac corresponding to a Young tableau of shape ν into elements
corresponding to a tableau of shape λ and a tableau of shape µ. In
particular, it shows that the number of such factorizations is independent of the content of the tableau. The quasi-crystal structure yields a
similar result for hypo.
Theorem 9.1. The number of distinct factorizations of an element
of the hypoplactic monoid corresponding to a quasi-ribbon tableau of
shape γ into elements that correspond to tableau of shape α and β is
dependent only of γ, α, and β, and not on the content of the element.
Proof. Let γ, α, β be compositions. Let w ∈ A∗n be a quasi-ribbon word
such that γ is the shape of QR(w). Let

w
= (u, v) : u, v ∈ A∗n are quasi-ribbon words,
Sα,β
QR(u) has shape α,
QR(v) has shape β,
w
Sα,β

w ≡hypo uv .

So
is a complete list of factorizations of w into elements whose
corresponding tableaux have shapes α and β. Let i ∈ {1, . . . , n − 1}
w
and suppose ëi (w) is defined. Pick some pair (u, v) ∈ Sα,β
. Then
w ≡hypo uv and so ëi (uv) is defined, and ëi (w) = ëi (uv). By Lemma

CRYSTALLIZING THE HYPOPLACTIC MONOID

51

5.4, either ëi (uv) = uëi (v), or ëi (uv) = ëi (u)v. In the former case,
(u, ëi (v)) ∈ Sëi (w) , and in the latter case (ëi (u), v) ∈ Sëi (w) , since ëi
preserves being a quasi-ribbon word and the shape of the corresponding
quasi-ribbon tableau by Corollary 6.2. So ëi induces an injective map
ëi (w)
w
from Sα,β
to Sα,β
. It follows that f¨i induces the inverse map from
ë (w)
ë (w)
Si
to S w . Hence |S w | = |S i |. Similarly, if f¨i (w) is defined,
α,β

α,β

α,β

w
|Sα,β
|

f¨i (w)
|Sα,β
|.

α,β

then
=
Since all the quasi-ribbon words whose tableaux
have shape γ lie in the same connected component of Γ(hypon ), it
w
follows that |Sα,β
| is dependent only on γ, not on w.

9.2. Conjugacy. There are several possibile generalizations of conjugacy from groups to monoids. One possible definition, introduced by
Otto [Ott84], is o-conjugacy, defined on a monoid M by
(9.1)

x ∼o y ⇐⇒ (∃g, h ∈ M )(xg = gy ∧ hx = yh).

The relation ∼o is an equivalence relation. Another approach is primary
conjugacy or p-conjugacy, defined on a monoid M by
x ∼p y ⇐⇒ (∃u, v ∈ M )(x = uv ∧ y = vu).
However, ∼p is reflexive and symmetric, but not transitive; hence it is
sensible to follow Kudryavtseva & Mazorchuk [KM09, KM07] in working with its transitive closure ∼∗p . It is easy to show that ∼p ⊆ ∼∗p ⊆ ∼o .
In some circumstances, equality holds. For instance, ∼∗p = ∼o in plac,
and two elements of plac are related by ∼∗p and ∼o if and only if they
have the same weight [CM13, Theorem 17]. Since hypo is a quotient of
plac, the same result holds in hypo, but the machinery of quasi-crystals
gives a very quick proof that two elements with the same weight are
∼o -related:
Proposition 9.2. Let u, v ∈ hypon be such that wt(u) = wt(v). Then
u ∼o v.
Proof. Let g = n(n−1) · · · 21. Then ug is highest-weight by Proposition
6.14, because it has an i-inversion for all i ∈ {1, . . . , n − 1}, and thus
no ëi is defined. Similarly gv is highest-weight. Furthermore, wt(ug) =
wt(u)+wt(g) = wt(v)+wt(g) = wt(gv). Hence ug ≡hypo gv. Similarly,
gu ≡hypo vg and so u ∼o v.

9.3. Satisfying an identity. Another application of the quasi-crystal
structure is to prove that the hypoplactic monoid satisfies an identity.
It is known that plac1 , plac2 , and plac3 satisfy identities, but whether
placn satisfies an identity (perhaps dependent on n) is an important
open problem [KO15].
Theorem 9.3. The hypoplactic monoid satisfies the identity xyxy =
yxyx.

52

ALAN J. CAIN AND ANTÓNIO MALHEIRO

Proof. Let x, y ∈ A∗n . The idea is to raise the products xyxy and
yxyx to highest-weight using the same sequence of operators ëi , deduce
that the corresponding highest-weight words are equal, and so conclude
that xyxy ≡hypo yxyx. More formally, the proof proceeds by reverse
induction on the weight of xyxy.
The base case of the induction is when xyxy is highest-weight. Thus
ëi (xyxy) is undefined for all i ∈ {1, . . . , n − 1}. So xyxy must have
an i-inversion for all i ∈ {1, . . . , max(xyxy) − 1}. The symbols i + 1
and i may each lie in x or y, but in any case, there is an i-inversion
in yxyx. Hence ëi (yxyx) is undefined for all i ∈ {1, . . . , n − 1}. So
yxyx is also highest-weight. Clearly wt(xyxy) = wt(yxyx), and so
QR(xyxy) = QR(yxyx) by Corollary 6.6. Hence xyxy ≡hypo yxyx.
For the induction step, suppose xyxy is not highest-weight, and that
0 0 0 0
x y x y ≡hypo y 0 x0 y 0 x0 for all x0 , y 0 ∈ A∗n such that x0 y 0 x0 y 0 has higher
weight than xyxy. Then ëi (xyxy) is defined for some i ∈ {1, . . . , n −
1}. Neither x nor y contains a symbol i, since otherwise there would
be an i-inversion in xyxy. So ¨i (xyxy) = ¨i (yxyx) = |xyxy|i+1 =
|yxyx|i+1 = 2|x|i+1 +2|y|i+1 = 2¨i (x)+2¨i (y), and ¨i (xyxy) applications
¨ (xyxy)
of i change every symbol i + 1 in xyxy to i. That is, ëi i
(xyxy) and
¨i (yxyx)
0 0 0 0
ëi
(yxyx) are both defined and are equal to x y x y and y 0 x0 y 0 x0
¨ (x)
¨ (y)
respectively, where x0 = ëi i (x) and y 0 = ëi i (y). Since x0 y 0 x0 y 0 has
higher weight than xyxy, it follows by the induction hypothesis that
x0 y 0 x0 y 0 ≡hypo y 0 x0 y 0 x0 . Hence
¨ (xyxy) 0 0 0 0
¨ (xyxy) 0 0 0 0
xyxy = f¨i i
(x y x y ) ≡hypo f¨i i
(y x y x ) = yxyx.

This completes the induction step and thus the proof.



References
[CGM]

A. J. Cain, R. D. Gray, & A. Malheiro. ‘Crystal monoids & crystal
bases: rewriting systems and biautomatic structures for plactic monoids
of types An , Bn , Cn , Dn , and G2 ’. arXiv: 1412.7040.
[CM13]
C. Choffrut & R. Mercaş. ‘The lexicographic cross-section of the plactic monoid is regular’. In Combinatorics on words, vol. 8079 of Lecture Notes in Comput. Sci., pp. 83–94. Springer, Heidelberg, 2013. doi:
10.1007/978-3-642-40579-2 11.
[FRT54] J. S. Frame, G. d. B. Robinson, & R. M. Thrall. ‘The hook graphs of
the symmetric groups’. Canadian J. Math., 6 (1954), pp. 316–324. doi:
10.4153/CJM-1954-030-1.
[Ful97]
W. Fulton. Young Tableaux, vol. 35 of London Mathematical Society
Student Texts. Cambridge University Press, Cambridge, 1997. With applications to representation theory and geometry.
[GKL+ 95] I. M. Gelfand, D. Krob, A. Lascoux, B. Leclerc, V. S. Retakh, & J. Y.
Thibon. ‘Noncommutative symmetric functions’. Adv. Math., 112, no. 2
(1995), pp. 218–348. doi: 10.1006/aima.1995.1032.
[Gre07]
J. A. Green. Polynomial representations of GLn , vol. 830 of Lecture
Notes in Mathematics. Springer, Berlin, augmented edition, 2007. With

CRYSTALLIZING THE HYPOPLACTIC MONOID

[Hag15]

[Hig92]
[Hiv00]

[HK02]

[How95]

[Jed11]

[Kas90]

[Kas91]

[KM07]

[KM09]

[KN94]

[Knu70]

[KO15]
[KS04]

[KT97]

[KT99]

53

an appendix on Schensted correspondence and Littelmann paths by K.
Erdmann, Green and M. Schocker.
N. Hage. ‘Finite convergent presentation of plactic monoid for type C’.
Internat. J. Algebra Comput., 25, no. 8 (2015), pp. 1239–1263. doi:
10.1142/S0218196715500393.
P. M. Higgins. Techniques of Semigroup Theory. Oxford Science Publications. Clarendon Press, Oxford University Press, New York, 1992.
F. Hivert. ‘Hecke algebras, difference operators, and quasi-symmetric
functions’. Adv. Math., 155, no. 2 (2000), pp. 181–238. doi:
10.1006/aima.1999.1901.
J. Hong & S. J. Kang. Introduction to quantum groups and crystal bases,
vol. 42 of Graduate Studies in Mathematics. American Mathematical
Society, Providence, RI, 2002. doi: 10.1090/gsm/042.
J. M. Howie. Fundamentals of Semigroup Theory, vol. 12 of London
Mathematical Society Monographs (New Series). Clarendon Press, Oxford University Press, New York, 1995.
F. Jedrzejewski. ‘Plactic classification of modes’. In Mathematics and
computation in music, vol. 6726 of Lecture Notes in Comput. Sci.,
pp. 350–353. Springer, Heidelberg, 2011. doi: 10.1007/978-3-642-215902 31.
M. Kashiwara. ‘Crystalizing the q-analogue of universal enveloping algebras’. Comm. Math. Phys., 133, no. 2 (1990), pp. 249–260. url:
http://projecteuclid.org/euclid.cmp/1104201397.
M. Kashiwara. ‘On crystal bases of the q-analogue of universal enveloping algebras’. Duke Math. J., 63, no. 2 (1991), pp. 465–516. doi:
10.1215/S0012-7094-91-06321-0.
G. Kudryavtseva & V. Mazorchuk. ‘On conjugation in some transformation and Brauer-type semigroups’. Publ. Math. Debrecen, 70, no. 1-2
(2007), pp. 19–43.
G. Kudryavtseva & V. Mazorchuk. ‘On three approaches to conjugacy
in semigroups’. Semigroup Forum, 78, no. 1 (2009), pp. 14–20. doi:
10.1007/s00233-008-9047-7.
M. Kashiwara & T. Nakashima. ‘Crystal graphs for representations of
the q-analogue of classical Lie algebras’. J. Algebra, 165, no. 2 (1994),
pp. 295–345. doi: 10.1006/jabr.1994.1114.
D. E. Knuth. ‘Permutations, matrices, and generalized Young tableaux’.
Pacific J. Math., 34 (1970), pp. 709–727. url: projecteuclid.org/
euclid.pjm/1102971948.
L. Kubat & J. Okniński. ‘Identities of the plactic monoid’. Semigroup
Forum, 90, no. 1 (2015), pp. 100–112. doi: 10.1007/s00233-014-9609-9.
J. A. Kim & D. U. Shin. ‘Insertion scheme for the classical lie algebras’.
Comm. Algebra, 32, no. 8 (2004), pp. 3139–3167. doi: 10.1081/AGB120039283.
D. Krob & J. Y. Thibon. ‘Noncommutative symmetric functions IV:
Quantum linear groups and Hecke algebras at q = 0’. J. Algebraic Combin., 6, no. 4 (1997), pp. 339–376. doi: 10.1023/A:1008673127310.
D. Krob & J. Y. Thibon. ‘Noncommutative symmetric functions. V.
A degenerate version of Uq (glN )’. Internat. J. Algebra Comput., 9,
no. 3-4 (1999), pp. 405–430. Dedicated to the memory of Marcel-Paul
Schützenberger. doi: 10.1142/S0218196799000254.

54

[Lec02]

[Lec03]

[Lec07]

[Lot02]

[LR34]

[LS78]

[LS81]

[LS85]

[LS90]

[Mac95]

[Nov00]

[Ott84]

[Ruš95]
[Sch61]
[Sch97]

[Shi05]
[Sta05]

ALAN J. CAIN AND ANTÓNIO MALHEIRO

C. Lecouvey. ‘Schensted-type correspondence, plactic monoid, and jeu
de taquin for type Cn ’. J. Algebra, 247, no. 2 (2002), pp. 295–331. doi:
10.1006/jabr.2001.8905.
C. Lecouvey. ‘Schensted-type correspondences and plactic monoids for
types Bn and Dn ’. J. Algebraic Combin., 18, no. 2 (2003), pp. 99–133.
doi: 10.1023/A:1025154930381.
C. Lecouvey. ‘Combinatorics of crystal graphs for the root systems of types An , Bn , Cn , Dn and G2 ’. In Combinatorial aspect of integrable systems, vol. 17 of Mathematical Society of
Japan Memoirs, pp. 11–41. Math. Soc. Japan, Tokyo, 2007. doi:
doi:10.2969/msjmemoirs/01701C020.
M. Lothaire. Algebraic Combinatorics on Words, vol. 90 of Encyclopedia of Mathematics and its Applications. Cambridge University Press,
Cambridge, 2002.
D. Littlewood & A. Richardson. ‘Group characters and algebra’. Philos.
Trans. Roy. Soc. London Ser. A, 233 (1934), pp. 99–141. url: http:
//www.jstor.org/stable/91293.
A. Lascoux & M. P. Schützenberger. ‘Sur une conjecture de H. O.
Foulkes’. C. R. Acad. Sci. Paris Sér. A-B, 286, no. 7 (1978), pp. A323–
A324.
A. Lascoux & M. P. Schützenberger. ‘Le monoı̈de plaxique’. In Noncommutative structures in algebra and geometric combinatorics (Naples,
1978), vol. 109 of Quad. “Ricerca Sci.”, pp. 129–156. CNR, Rome, 1981.
A. Lascoux & M. P. Schützenberger. ‘Schubert polynomials and the
Littlewood-Richardson rule’. Lett. Math. Phys., 10, no. 2-3 (1985), pp.
111–124. doi: 10.1007/BF00398147.
A. Lascoux & M. P. Schützenberger. ‘Tableaux and noncommutative
Schubert polynomials’. Funct. Anal. Appl., , no. 23 (1990), pp. 223–225.
doi: 10.1007/BF01079531.
I. Macdonald. Symmetric functions and Hall polynomials. Oxford Mathematical Monographs. The Clarendon Press, Oxford University Press,
New York, second edition, 1995. With contributions by A. Zelevinsky,
Oxford Science Publications.
J. C. Novelli. ‘On the hypoplactic monoid’. Discrete Math., 217, no. 1-3
(2000), pp. 315–336. Formal power series and algebraic combinatorics
(Vienna, 1997). doi: 10.1016/S0012-365X(99)00270-8.
F. Otto. ‘Conjugacy in monoids with a special Church-Rosser presentation is decidable’. Semigroup Forum, 29, no. 1-2 (1984), pp. 223–240.
doi: 10.1007/BF02573327.
N. Ruškuc. Semigroup Presentations. Ph.D. Thesis, University of St
Andrews, 1995. url: hdl.handle.net/10023/2821.
C. Schensted. ‘Longest increasing and decreasing subsequences’. Canad.
J. Math., 13 (1961), pp. 179–191. doi: 10.4153/CJM-1961-015-3.
M. P. Schützenberger. ‘Pour le monoı̈de plaxique’. Math. Inform. Sci.
Humaines, , no. 140 (1997), pp. 5–10. url: www.ehess.fr/revue-msh/
pdf/N140R764.pdf.
M. Shimozono. ‘Crystals for dummies’. Notes, 2005. url: www.aimath.
org/WWN/kostka/crysdumb.pdf.
R. P. Stanley. Enumerative Combinatorics (Vol.2). Cambridge University Press, 2005.

CRYSTALLIZING THE HYPOPLACTIC MONOID

[Sta12]

[Ste03]

55

R. P. Stanley. Enumerative Combinatorics (Vol. 1), vol. 49 of Cambridge Studies in Advanced Mathematics. Cambridge University Press,
Cambridge, second edition, 2012.
J. R. Stembridge. ‘A local characterization of simply-laced crystals’.
Trans. Amer. Math. Soc., 355, no. 12 (2003), pp. 4807–4823 (electronic).
doi: 10.1090/S0002-9947-03-03042-3.

Centro de Matemática e Aplicações, Faculdade de Ciências e Tecnologia, Universidade Nova de Lisboa, 2829–516 Caparica, Portugal
E-mail address: a.cain@fct.unl.pt
Centro de Matemática e Aplicações, Faculdade de Ciências e Tecnologia, Universidade Nova de Lisboa, 2829–516 Caparica, Portugal
Departamento de Matemática, Faculdade de Ciências e Tecnologia,
Universidade Nova de Lisboa, 2829–516 Caparica, Portugal
E-mail address: ajm@fct.unl.pt

