CRYSTALS AND TREES: QUASI-KASHIWARA
OPERATORS, MONOIDS OF BINARY TREES, AND
ROBINSON–SCHENSTED-TYPE CORRESPONDENCES

arXiv:1702.02998v2 [math.CO] 1 Feb 2018

ALAN J. CAIN AND ANTÓNIO MALHEIRO
Abstract. Kashiwara’s crystal graphs have a natural monoid structure
that arises by identifying words labelling vertices that appear in the same
position of isomorphic components. The celebrated plactic monoid (the
monoid of Young tableaux), arises in this way from the crystal graph
for the q-analogue of the general linear Lie algebra gln , and the socalled Kashiwara operators interact beautifully with the combinatorics
of Young tableaux and with the Robinson–Schensted–Knuth correspondence. The authors previously constructed an analogous ‘quasi-crystal’
structure for the related hypoplactic monoid (the monoid of quasi-ribbon
tableaux), which has similarly neat combinatorial properties. This paper constructs an analogous ‘crystal-type’ structure for the sylvester and
Baxter monoids (the monoids of binary search trees and pairs of twin binary search trees, respectively). Both monoids are shown to arise from
this structure just as the plactic monoid does from the usual crystal
graph. The interaction of the structure with the sylvester and Baxter
versions of the Robinson–Schensted–Knuth correspondence is studied.
The structure is then applied to prove results on the number of factorizations of elements of these monoids, and to prove that both monoids
satisfy non-trivial identities.

1. Introduction
Kashiwara’s notion of a crystal basis [Kas90, Kas91] (informally, a basis
of a representation for a suitable algebra on which the generators have a
particularly straightforward action), gives rise, via tensor products, to the
crystal graph. This graph has a natural monoid structure where the vertices
are viewed as words in the free monoid, and words are identified when they
lie in the same places in isomorphic components of this graph. In the case of
the q-analogue of the general linear Lie algebra gln , the monoid obtained is
the celebrated plactic monoid, whose elements can be identified with Young
tableaux and which appears in such diverse contexts as symmetric functions
[Mac08], representation theory [Gre06], algebraic combinatorics [Lot02], algebraic geometry [Ful97], Kostka–Foulkes polynomials [LS81, LS78], Schubert polynomials [LS85, LS90], and musical theory [Jed11]. (Indeed, since
The first author was supported by an Investigador FCT fellowship
(IF/01622/2013/CP1161/CT0001).
For both authors, this work was partially supported by 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), and the project
PTDC/MHC-FIL/2583/2014.
The authors thank the anonymous referee for carefully reading the paper and for valuable comments, and, in particular, for making the observation contained in Remark 3.4.
1

2

ALAN J. CAIN AND ANTÓNIO MALHEIRO

Lascoux and Schützenberger’s [LS81] seminal study, so many connections
have emerged that Schützenberger proclaimed it ‘one of the most fundamental monoids in algebra’ [Sch97].) The beautiful interaction of the crystal graph and the associated Kashiwara operators with the combinatorics
of Young tableaux and the Robinson–Schensted correspondence is such an
important and powerful combinatorial tool that in this context the Kashiwara operators and crystal graph are sometimes simply referred to as the
‘coplactic’ operators and ‘coplactic’ graph (see, for instance, [Lot02, § 5.5]
and [vL01]).
In a previous paper [CM17], the present authors constructed an analogue of this crystal structure for the monoid of quasi-ribbon tableaux: the
so-called hypoplactic monoid. The hypoplactic monoid emerged from the
theory of non-commutative symmetric functions and quasi-symmetric functions [KT97, KT99, Nov00]. Quasi-ribbon functions form a basis for the
ring of quasi-symmetric functions, just as the Schur polynomials form a basis for the ring of symmetric polynomials. The quasi-ribbon functions are
indexed by the so-called quasi-ribbon tableaux, which can be identified with
the elements of the hypoplactic monoid. As shown in the authors’ previous paper, much of the elegant interaction of the crystal graph, Kashiwara
operators, Young tableaux, and the plactic monoid is echoed in the interaction of the analoguous quasi-crystal graph, quasi-Kashiwara operators,
quasi-ribbon tableaux, and the hypoplactic monoid.
Thus both plactic and hypoplactic monoids can be defined by factoring
the free monoid by a relation that can be defined in three equivalent ways:
1. Defining relations: the relation is the smallest congruence containing
a given set of defining relations.
2. Insertion: the relation is the kernel of the map that takes a word to
a ‘tableau-type’ object computed by an insertion algorithm.
3. Crystals: the relation arises from isomophisms of connected components of a ‘crystal-type’ graph.
The main aim of this paper is to develop an analoguous of the crystaltype structure for the sylvester [HNT05] and Baxter [Gir12] monoids, whose
elements are respectively right strict binary search trees and pairs of twin
binary search trees. To be more precise: the existing literature contains
equivalent definitions for these monoid using defining relations and insertions
algorithms (approaches 1 and 2 above). This paper develops and applies the
crystalline definition (approach 3 above).
In fact, the crystal-type graph for the sylvester and Baxter monoids are
the same as for the hypoplactic monoid: it is the notion of isomorphism
that has to be modified. This paper develops an abstract framework for
this modified notion of isomorphism (Section 5), and then applies it to the
sylvester and Baxter monoids (Sections 6 and 7).
This framework is developed from a slightly different perspective from the
authors’ earlier paper on the hypoplactic monoid. Essentially, the difference
is that rather than having finitely many Kashiwara and ‘quasi-Kashiwara’
operators, countably many are allowed, and the resulting monoids have infinite rank rather than finite rank. This is a step away from the representationtheoretic origin of crystal bases, but is actually a much more natural context

CRYSTALS AND TREES

3

for a combinatorially-focussed study. More importantly, it seems to be the
correct starting-point to crystallize other monoids connected with combinatorics, such as sylvester and Baxter monoids. In order to discuss the
advantages of these modified graphs and to clarify what properties a ‘crystal structure’ for the sylvester and Baxter monoids should enjoy, Section 3
briefly recapitulates some of the existing theory. Although some of this material is in existing literature, the important differences between the finiteand infinite-rank cases are often glossed over.
The resulting crystal-type structure for the sylvester and Baxter monoids
turns out to interact neatly with the sylvester and Baxter versions of the
Robinson–Schensted correspondence, and yield new results.

2. Preliminaries and notation
Much of the notation used in this paper is drawn from [CM17], to which
this paper is a sequel. For definitions and notation for alphabets, words, presentations, standard words, standardization, partitions, compositions, and
weight see [CM17, § 2]. For Young tableaux, the Schensted insertion algorithm, and the definition of the plactic monoid plac and rank-n plactic
monoid placn using these, see [CM17, § 3.1]; note however that the present
paper uses Pplac (u) and Qplac (u) respectively for the Young tableau and
recording tableau computed from u ∈ A∗ and calls these the plactic P- and
Q-symbols of u. Similarly Phypo (u) and Qhypo (u) are respectively the quasiribbon tableau and recording ribbon computed from u ∈ A∗ and calls these
the hypoplactic P- and Q-symbols of u. This is to keep notation uniform
with the analogous notions for the sylvester and Baxter monoids.
Note that the defining relations Rplac given in [CM17, § 1] (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 [CM17] and the present paper are mainly
concerned with combinatorics, rather than representation theory, they follow
Shimozono [Shi05] in using the convention that is compatible with the usual
notions of Young tableaux and the Robinston–Schensted correspondence.
For quasi-ribbon tableaux and the Schensted insertion algorithm, and the
definition of the hypoplactic monoid hypo and rank-n hypoplactic monoid
hypon using these, see [CM17, § 4].

3. Infinite-rank crystals and quasi-crystals
This section recalls the definitions of the Kashiwara and quasi-Kashiwara
operators, defines the infinite-rank crystal and quasi-crystal graphs, and
shows that isomorphisms between components of these graphs give rise,
respectively to the plactic and hypoplactic monoids. Many of the proofs in
this section are not given in full, since they are straightforward modifications
of the proofs for finite-rank crystal and quasi-crystal graphs given in [CM17,
§§ 3 and 5].

4

ALAN J. CAIN AND ANTÓNIO MALHEIRO

3.1. Crystal graph and the plactic monoid. Let i ∈ N and define the
Kashiwara operators ẽi and f˜i on A as follows:
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∗ \ A 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} : f˜i · · · f˜i (w) is defined .
| {z }
k times

(Note that this definition is in a sense the mirror image of [KN94, Theorem 1.14], 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 in [CM17] and
[Shi05, p. 8].)
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). Thus ẽi and f˜i are
respectively called the Kashiwara raising and lowering operators. Furthermore, a word on which none of the ẽi is defined is said to be highest-weight.
The crystal graph for plac, denoted Γ(plac), is the directed labelled graph
with vertex set A∗ and, for u, v ∈ A∗ , an edge from u to v labelled by i if and
only if v = f˜i (u) (or, equivalently, u = ẽi (v)). Figure 1 shows part of the
crystal graph Γ(plac). For any w ∈ A∗ , let Γ(plac, w) denote the connected
component of Γ(plac) that contains the vertex w. For n ∈ N, the crystal
graph for placn , denoted Γ(placn ), is the subgraph of Γ(plac) induced by A∗n .
Notice that edge labels in Γ(placn ) must lie in {1, . . . , n − 1}, since for i ≥ n,
if f˜i (u) is defined, then at least one of u and f˜i (u) does not lie in A∗n .
Define a relation ≈ on A∗ as follows: u ≈ v if and only if there is a labelled
digraph isomorphism θ : Γ(plac, u) → Γ(plac, v) with θ(u) = v. That is,
u ≈ v if u and v lie in corresponding places in isomorphic components of
Γ(plac).
It is worth emphasizing that the definition of ≈ is the crucial point of
divergence from the standard approach to crystals: normally, as in [CGM,
§ 2.4], ≈ is defined in terms of weight-preserving isomorphisms.
Proposition 3.1 ([CGM, Proposition 2.6]). The relation ≈ is a congruence
on A∗ .
(Strictly speaking, the preceding result follows by modifying the proof of
[CGM, Proposition 2.6] by replacing An with A and ignoring the discussion
of weight.)

CRYSTALS AND TREES

5

2111
1

2

3111
1

2112
3

3112
1

3122
1

3222

1

2

4111
3

1

4112
3

1

4122

2113
4

2

5111
2

4

4113

2
1

5112

6111

3

3113
1

5

2122

3123

1

2

2114
3

2

3114

2123
4

1

2115

2

3

2133

2124

Figure 1. Part of the connected component Γ(plac, 2111).
Theorem 3.2 ([Lot02, Theorem 5.5.1]). Let u, v ∈ A∗ .
(1) Qplac (u) = Qplac (ẽi (u)) if ẽi (u) is defined and similarly for f˜i .
(2) Suppose u ≡plac v. Then ẽi (u) is defined if and only if ẽi (v) is
defined, in which case ẽi (u) ≡plac ẽi (v) and similarly for f˜i .
(To be strict, [Lot02, Theorem 5.5.1] is concerned only with words in A∗n
and i ∈ {1, . . . , n − 1}. To obtain the result as stated here, one simply
chooses n to be bigger than the maximum symbol that appears in u or v.)
Proposition 3.3. The relations ≡plac and ≈ coincide.
Proof. Let u ∈ A∗ and i ∈ N. By iterated application of Theorem 3.2(2), if
u, v ∈ A∗ are such that u ≡plac v, then there is a labelled digraph isomorphism θ : Γ(plac, u) → Γ(plac, v) with θ(u) = v.
For the converse, let u, v ∈ A∗ and suppose there is a labelled digraph
isomorphism θ : Γ(plac, u) → Γ(plac, v) with θ(u) = v. If ẽi (u) is defined for
some i ∈ N, so is ẽi (v) (since θ is a labelled digraph isomorphism); thus one
can replace u and v with ẽi (u) and ẽi (v). Eventually one obtains highest
weight words u′ and v ′ . By the proof of [Lot02, Proposition 5.5.2], u′ and
v ′ are Yamanouchi words.
Suppose n is the largest symbol appearing in u′ . Then |u′ |n is the length of
the longest directed path in Γ(plac) made up of edges labelled by n starting at
|u′ |
u′ , or equivalently, φ̃n (u′ ). Furthermore, |u′ |n−1 = |f˜n n (u′ )|n−1 is equal to
|u′ |
φ̃n−1 (f˜n n (u′ )). Continuing in this way, one sees that for each i ∈ {1, . . . , n}

′
′
|u′ |
|u′ |
|u′ |i = |f˜i+1i+1 · · · f˜n|u |n (u′ )|i = φ̃i f˜i+1i+1 · · · f˜n|u |n (u′ ) .

Hence wt(u′ ) is determined by the connected component Γ(plac, u′ ). Similarly, wt(v ′ ) is determined by the connected component Γ(plac, v ′ ).

6

ALAN J. CAIN AND ANTÓNIO MALHEIRO

Since the components Γ(plac, u′ ) and Γ(plac, v ′ ) are isomorphic, wt(u′ ) =
wt(v ′ ). Thus, since u′ and v ′ are Yamanouchi words, Pplac (u′ ) and Pplac (v ′ )
are both equal to the tableaux of shape wt(u′ ) = wt(v ′ ) containing only symbols i on row i. Hence u′ ≡plac v ′ . By iterated application of Theorem 3.2(2),
w ≡plac θ(w) for all w ∈ Γ(plac, u).

In the finite rank case, the analogy of Proposition 3.3 does not hold: for
example, the connected components Γ(placn , ε) and Γ(placn , n(n − 1) · · · 21)
both consist of single vertices and thus are isomorphic as labelled digraphs.
(Thus [Lot02, Proposition 5.5.2] is technically false as stated.) This is the
crucial difference between the infinite-rank and finite-rank cases: In the
infinite-rank case, all necessary information about weights is contained in
the abstract graph Γ(plac) and so it suffices to consider labelled digraph
isomorphisms between connected components. However, in the finite-rank
case, the abstract graph Γ(placn ) does not contain sufficient information to
define the plactic monoid placn , and so it is necessary to restrict to weightpreserving labelled digraph isomorphisms.
Remark 3.4. In fact, the abstract graph Γ(placn ) is the crystal graph
for sln . This corresponds to the fact that quotienting by the full column
n(n − 1) · · · 21 projects from isomorphism classes of gln crystal graphs to
isomorphism classes of sln crystal graphs. The only extra information one
requires to reverse this projection is how many full columns are present.
3.2. Quasi-crystal graph and the hypoplactic monoid. Let i ∈ N.
Define the quasi-Kashiwara operators ëi and f¨i on A∗ as follows: Let u ∈ A∗ .
• If u contains a subsequence (i + 1)i, both ëi (u) and f¨i (u) are undefined.
• If u does not contain a subsequence (i + 1)i, but u contains at least
one symbol i+1, then ëi (u) is the word obtained from u by replacing
the left-most symbol i + 1 by i; if u contains no symbol i + 1, then
ëi (u) is undefined.
• If u does not contain a subsequence (i + 1)i, but u contains at least
one symbol i, then f¨i (u) is the word obtained from u by replacing
the right-most symbol i by i + 1; if u contains no symbol i, then
f¨i (u) is undefined.
(As in [CM17], a subsequence may be made up of non-consecutive letters;
thus the phrase ‘contains a subsequence (i + 1)i’ is equivalent to ‘contains a
symbol i + 1 somewhere to the left of a symbol i’.) For example,
ë2 (3123) is undefined since 3123 contains the subsequence 32;
f¨2 (3131) is undefined since 3131 does not contains a symbol 2;
f¨1 (3113) = 3123.
Lemma 3.5 ([CM17, Lemma 1]). For all i ∈ N, 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)).
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)) >

CRYSTALS AND TREES

7

1212
2

1213
3

2

1214
4

1313
2

1215
5

1314
2

1216
6

1217

1

3

4

1323

1315
2

5

1316

1

3

1414

3

1

1324

3
1

1
4

1325

4

1415

2323
3

1424

1

3

2324

Figure 2. Part of the connected component Γ(hypo, 1212).

wt(u), and if f¨i (u) is defined, then wt(f¨i (u)) < wt(u). Thus ëi and f¨i
are respectively called the quasi-Kashiwara raising and lowering operators.
Furthermore, a word on which none of the ëi is defined is said to be highestweight. (Strictly speaking, it is necessary to distinguish words that are
highest-weight with respect to the operators ëi and words that are highestweight with respect to the operators ẽi . Since the ẽi are not mentioned in
the remainder of the paper, the term ‘highest-weight’ will always be with
respect to the operators ëi .)
The quasi-crystal graph for hypo, denoted Γ(hypo), is the directed labelled
graph with vertex set A∗ and, for u, v ∈ A∗ , an edge from u to v labelled by
i if and only if v = f˜i (u) (or, equivalently, u = ẽi (v)). Figure 2 shows part of
the crystal graph Γ(hypo). For any w ∈ A∗ , let Γ(hypo, w) denote the connected component of Γ(hypo) that contains the vertex w. The quasi-crystal
graph for hypon , denoted Γ(hypon ), is the subgraph of Γ(hypo) induced by
A∗n . Notice that edge labels in Γ(hypon ) must lie in {1, . . . , n − 1}, since for
i ≥ n, if f¨i (u) is defined, then at least one of u and f¨i (u) does not lie in A∗n .
Define a relation ∼ on A∗ as follows: u ∼ v if and only if there is a labelled
digraph isomorphism θ : Γ(hypo, u) → Γ(hypo, v) with θ(u) = v. That is,
u ∼ v if u and v lie in corresponding places in isomorphic components of
Γ(hypo). For instance, as can be seen in Figure 3, 1241 ∼ 2141.
Again, note that the definition of ∼ is the point of divergence from the previous definition in [CM17], where ∼ is defined in terms of weight-preserving
isomorphisms.

8

ALAN J. CAIN AND ANTÓNIO MALHEIRO

By the proof of [CM17, Proposition 4], replacing An with A and ignoring
the discussion of weight, the relation ∼ is a congruence on A∗ .
Proposition 3.6 ([CM17, Proposition 5]). Let u ∈ A∗ and i ∈ N.
(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).
In contrast to Proposition 3.6, the usual Kashiwara operators do not preserve standardization: ẽ2 (1322) = 1323, but std(1322) = 1423 6= 1324 =
std(1323).
Proposition 3.7. The relations ≡hypo and ∼ coincide.
Proof. Let u, v ∈ A∗ .
Suppose that u ≡hypo v. Using the reasoning that leads to the proof of
[CM17, Proposition 8], but replacing An by A, proves that u ∼ v.
Now suppose that there is a labelled digraph isomorphism θ : Γ(hypo, u) →
Γ(hypo, v) with θ(u) = v. Then there is a sequence of operators ëi1 , . . . , ëik
such that the words u′ = ëi1 · · · ëik (u) and v ′ = ëi1 · · · ëik (v) are highestweight. By the same reasoning as in Proposition 3.3, wt(u′ ) and wt(v ′ )
are determined by the isomorphic connected components Γ(hypo, u) and
Γ(hypo, v), and thus wt(u′ ) = wt(v ′ ). Since u′ ≡hypo C(Phypo (u′ )), and
v ′ ≡hypo C(Phypo (v ′ )) by [CM17, Lemmata 5 and 6] (replacing An by A),
and C(Phypo (u′ )) and C(Phypo (v ′ )) are highest-weight (since ≡hypo ⊆ ∼hypo
by the first part) and have the same weight, C(Phypo (u′ )) = C(Phypo (v ′ )) by
[CM17, Corollary 3]. Hence u′ ≡hypo C(Phypo (u′ )) = C(Phypo (v ′ )) ≡hypo v ′ .
By [CM17, Lemma 6(2)], applying f¨i to ≡hypo -related words yields ≡hypo related words. Hence u ≡hypo v.

In the finite rank case, the analogy of Proposition 3.7 does not hold: the
connected components Γ(hypon , ε) and Γ(hypon , n(n−1) · · · 21) both consist
of single vertices and thus are isomorphic as labelled digraphs. This is again
the crucial difference between the infinite-rank and finite-rank cases: In the
infinite-rank case, all necessary information about weights is contained in
the abstract graph Γ(hypo) and so it suffices to consider labelled digraph
isomorphisms between connected components. However, in the finite-rank
case, the abstract graph Γ(hypon ) does not contain sufficient information,
and so it is necessary to restrict to weight-preserving labelled digraph isomorphisms.
There is a very neat interaction between the structure of Γ(hypo) and the
hypoplactic analogue of the Robinson–Schensted correspondence; the proof
for the finite-rank case applies in the infinite-rank case:
Theorem 3.8 ([CM17, Theorem 2]). Let u, v ∈ A∗ . The words u and v lie in
the same connected component of Γ(hypo) if and only if Qhypo (u) = Qhypo (v).
Thus the recording ribbons Qhypo (·) produced by the insertion algorithm
(see the exposition in [CM17, § 4]) index connected components of Γ(hypo).
However, in the infinite-rank case, connected components are also indexed
by standard words, as shown in Corollary 3.10 below.
Lemma 3.9. For any u ∈ A∗ , the equality Qhypo (std(u)) = Qhypo (u) holds.

CRYSTALS AND TREES

Γ(hypo, 1212)
}|

z

1212

{

2

2

1215

3

2

3

1314

1

4

1323

2151

1221

{

1231
2

2141

1313

Γ(hypo, 1221)
}|

z

2

2131

1214
4

2121

{

2

1213
3

Γ(hypo, 2121)
}|

z

9

3

3131
2

3

3141

2

1241
1

4

3231

1251

1331
2

3

1341

1

1332

Figure 3. The isomorphic components Γ(hypo, 1212),
Γ(hypo, 2121), and Γ(hypo, 1221) of the quasi-crystal graph
Γ(hypo).
Proof. Let u = u1 · · · uk and std(u) = s1 · · · sk , where uh , sh ∈ A. Since
std(u1 · · · uk ) = std(s1 · · · sk ), it follows that std(u1 · · · uh ) = std(s1 · · · sh )
for all h (this is immediate from the definition of standardization [Nov00,
Lemma 2.2]). Thus, by [Nov00, Theorems 4.12 and 4.16], Qhypo (u1 · · · uh )
and Qhypo (s1 · · · sh ) both have shape DC(std(u1 · · · uh )−1 ) for all h. The
sequence of these shapes determines where new symbols are inserted during
the computation of Phypo (u) and Qhypo (std(u)) by [CM17, Algorithm 4], and
so Qhypo (u) = Qhypo (std(u)).

Corollary 3.10. In every connected component of Γ(hypo), there is exactly
one standard word, and so for all u, v ∈ A∗ , the words u and v lie in the
same connected component if and only if std(u) = std(v).
Proof. By Lemma 3.9 and Theorem 3.8, u and std(u) are in the same component of Γ(hypo), so each connected component contains at least one standard
word. Suppose u′ is a standard word in the same component of Γ(hypo) as
u. Then it is possible to apply a sequence of quasi-Kashiwara operators to
u and obtain u′ . By Proposition 3.6, quasi-Kashiwara operators preserve
standardization; thus std(u) = std(u′ ) and so u = u′ since u and u′ are
standard words. The last claim in the statement follows immediately.

Remark 3.11. As noted in [CM17], a related notion of ‘quasi-crystal’ is
found in Krob and Thibon [KT99]; see also [Hiv00]. However, the Krob–
Thibon quasi-crystal describes the restriction to quasi-ribbon tableaux (or
rather corresponding to quasi-ribbon tableaux) of the action of the usual
Kashiwara operators: it does not apply to all words and so does not yield a
definition of ≡hypo via isomorphisms of components.

10

ALAN J. CAIN AND ANTÓNIO MALHEIRO

4. Binary trees and the sylvester and Baxter monoids
This section gathers the necessary definitions and background on binary search trees, the sylvester and Baxter monoids, and the analogues
of the Robinson–Schensted correspondence. For further background on the
sylvester monoid, see [HNT05]; for the Baxter monoid, see [Gir12].
4.1. Binary trees and insertion. A left strict binary search tree is a labelled rooted binary tree where the label of each node is strictly greater
than the label of every node in its left subtree, and less or equal to than the
label of every node in its right subtree. A right strict binary search tree is
a labelled rooted binary tree where the label of each node is greater than
or equal to the label of every node in its left subtree, and strictly less than
the label of every node in its right subtree. The following are examples of,
respectively, left strict and right strict binary search trees:
5

4

4

(4.1)

1

5
4

2
7

1

6
2

1

5
4

1

5

.

6

5

7

5

A binary search tree is standard if the labels of its nodes are exactly the
integers from 1 to the number of nodes in the tree. The shape of a binary
search tree T , denoted Sh(T ), is simply its underlying unlabelled rooted
binary tree. The notion of shape will be important later in the paper.
A decreasing tree is a labelled rooted binary tree where the label of each
node is greater than the label of its children. An increasing tree is a labelled
rooted binary tree where the label of each node is less than the label of its
children. The following are examples of, respectively, standard increasing
and standard decreasing trees:
1

10

2

(4.2)

4

3
10

7

6
9

9
5

7
4

8
2

3
1

.

6
5

8

The left-to-right infix traversal (or simply the infix traversal) of a rooted
binary tree T is the sequence that ‘visits’ every node in the tree as follows:
it recursively performs the infix traversal of the left subtree of the root of T ,
then visits the root of T , then recursively performs the infix traversal of the
right subtree of the root of T . Thus the infix traversal of any binary tree
with the same shape as the right-hand tree in (4.1) visits nodes as follows:
(4.3)

.

The left-to-right postfix traversal, or simply the postfix traversal, of a rooted
binary tree T is the sequence that ‘visits’ every node in the tree as follows:

CRYSTALS AND TREES

11

it recursively perform the postfix traversal of the left subtree of the root
of T , then recursively perform the postfix traversal of the right subtree of
the root of T , then visits the root of T . Thus the postfix traversal of any
binary tree with the same shape as the right-hand tree in (4.1) visits nodes
as follows:

(4.4)

.

The infix reading In(T ) (respectively, postfix reading Post(T )) of a labelled
binary search tree T is defined to be the word obtained by listing the labels
of the nodes visited during the infix (respectively, postfix) traversal. For
example, the infix and postfix readings of the right-hand tree in (4.1) are,
respectively, 1124455567 and 1142557654. Note that the weights of the
infix and postfix readings of a given binary search tree are the same; both
weights are simply the tuple that describes the number of each symbol in
A appearing in the tree. Thus define the weight of a labelled binary search
tree to be the weight of these readings.
The following result is immediate from the definition of a binary search
tree, but it is used frequently:
Proposition 4.1. For any (left or right strict) binary search tree T , the
infix reading In(T ) is always the unique weakly increasing word with the
same weight as T .
Let T be a rooted binary tree and let x1 , . . . , xm be the nodes of T in the
order visited in an infix traversal. Let i1 , . . . , ik−1 be such that the xih are
precisely the nodes of T that have non-empty left subtrees. The left interval
partition of T is the partition
o
n
{x1 , . . . , xi1 −1 }, {xi1 , . . . , xi2 −1 }, . . . , {xik−2 , . . . , xik−1 −1 }, {xk−1 , . . . , xm } ;
{z
} |
{z
}
{z
}
|
{z
} |
|
1st left interval

2nd left interval

k − 1-th left interval

k-th left interval

the h-th part of this partition is the h-th left interval of T . Let j1 , . . . , jℓ−1
be such that the xjh are precisely the nodes of T that have non-empty right
subtrees. The right interval partition of T is the partition
o
n
{x1 , . . . , xj1 } , {xj1 +1 , . . . , xj2 }, . . . , {xjℓ−2 +1 , . . . , xjℓ−1 }, {xℓ−1 , . . . , xm } ;
{z
}
|
{z
} |
{z
}
{z
} |
|
1st right interval

2nd right interval

ℓ − 1-th right interval

ℓ-th right interval

the h-th part of this partition is the h-th right interval of T . Consider the
left and right intervals of a binary tree with the same shape as the right-hand
tree in (4.1). Then the nodes lying in the left intervals and right intervals
of this tree are, respectively, those linked by solid lines in the left-hand and
right-hand diagrams below:
4th
3rd

(4.5)

6th

2nd
1st

4th
5th

1st

2nd

3rd

5th

12

ALAN J. CAIN AND ANTÓNIO MALHEIRO

In a sense, the lengths of the left and right intervals of a binary seach tree
are analogous to the lengths of the rows in a quasi-ribbon tableau. However,
the lengths of left and right intervals do not determine the shape of the tree,
for the trees
and
both have left interval length 2, 2 and right interval lengths 1, 2, 1:
;

.

The canopy of a binary tree T , denoted cnp(T ) is the word over {0, 1} obtained by doing an infix traversal of the nodes of T and outputting a 1 when
an empty left subtree is encountered and 0 when an empty right subtree is
encountered, then omitting the 1 from the start and the 0 from the end of
the resulting word. (These symbols correspond to the empty left subtree
of the leftmost node and the empty right subtree of the rightmost node.)
For example, the canopies of the two binary trees in (4.1) are, respectively,
110101100 and 001010011:
5
4

(4.6)

1
1

1

4
1

4

6
2

0 1

2
7

0

1
1

5

5

0

1
1

0

0 1

5
4

0

1

5

5
0

0 1

.

6
1

7

0

Let TL and TR be binary trees. Then (TL , TR ) is a pair of twin binary
trees if cnp(TL ) and cnp(TR ) are complementary, in the sense that for all i,
the i-th symbols of cnp(TL ) and cnp(TR ) are unequal.
Now let TL be a left strict binary search tree and let TR be a right strict
binary search tree. Then (TL , TR ) is a pair of twin binary search trees if
In(TL ) = In(TR ) and cnp(TL ) and cnp(TR ) are complementary (that is, the
underlying binary trees form a pair of twin binary trees). Note that the
binary search trees in (4.1) form a pair of twin binary search trees, since
they have the same infix reading (that is, 1124455567), and complementary
canopies, as shown in (4.6). The shape of a pair of twin binary search trees
(TL , TR ), denoted Sh(TL , TR ), is simply the underlying pair of unlabelled
rooted binary trees.
The insertion algorithms for right (respectively, left) strict binary search
trees adds the new symbol as a leaf node in the unique place that maintains
the property of being a right (respectively, left) strict binary search tree.
Algorithm 4.2 (Left strict leaf insertion).
Input: A left strict binary search tree T and a symbol a ∈ A.
Output: A left strict binary search tree T ← a.
Method: If T is empty, create a node and label it a. If T is non-empty,
examine the label x of the root node; if a ≥ x, recursively insert a into the
right subtree of the root node; otherwise recursively insert a into the left
subtree of the root note. Output the resulting tree.

CRYSTALS AND TREES

13

Algorithm 4.3 (Right strict leaf insertion).
Input: A right strict binary search tree T and a symbol a ∈ A.
Output: A right strict binary search tree a → T .
Method: If T is empty, create a node and label it a. If T is non-empty,
examine the label x of the root node; if a ≤ x, recursively insert a into the
left subtree of the root node; otherwise recursively insert a into the right
subtree of the root note. Output the resulting tree.
Using the leaf insertion algorithms described above, we can compute from
a word in A∗ a left (respectively, right) binary search tree.
Algorithm 4.4 (Left strict insertion).
Input: A word a1 · · · ak , where ai ∈ A.
Output: A left strict binary search tree TL (a1 · · · ak ) and a standard increasing tree TRecL (a1 · · · ak ).
Method: Start with the empty binary search tree T0 and an empty increasing tree D0 . For each i = 1, . . . , k, insert ai into Ti−1 as per Algorithm 4.2;
let Ti be the resulting binary search tree. Build a increasing tree Di that
has the same shape as Ti by adding a node labelled by i to the tree Di−1 in
the same place as ai was inserted into Ti−1 .
Output Tk for TL (a1 · · · ak ) and Dk for TRecL (a1 · · · ak ).
Algorithm 4.5 (Right strict insertion).
Input: A word a1 · · · ak , where ai ∈ A.
Output: A right strict binary search tree TR (a1 · · · ak ) and a standard
decreasing tree TRecR (a1 · · · ak ).
Method: Start with the empty binary search tree T0 and an empty decreasing tree D0 . For each i = 1, . . . , k, insert ak−i+1 into Ti−1 as per
Algorithm 4.3; let Ti be the resulting binary search tree. Build a decreasing
tree Di that has the same shape as Ti by adding a node labelled by k − i + 1
to the tree Di−1 in the same place as ak−i+1 was inserted into Ti−1 .
Output Tk for TR (a1 · · · ak ) and Dk for TRecR (a1 · · · ak ).
For example, if u = 5451761524, then TL (u) and TR (u) are respectively
the left- and right-hand trees in (4.1), and TRecL (u) and TRecR (u) are
respectively the left- and right-hand trees in (4.2). Note that Algorithm 4.4
proceeds through the word from left to right, while Algorithm 4.5 proceeds
through the word from right to left.
Let u ∈ A∗ be a word that contains no repeated symbols. The decreasing
tree of u, denoted DecT(u), is defined as follows: if m is the maximum
symbol that appears in u, so that u = sms′ , then DecT(u) has root labelled
by m, and the left subtree of its root is DecT(s) and the right subtree of the
root is DecT(s′ ). That is,

DecT(u) = DecT sms′ =

m

.
DecT(s)

DecT(s′ )

Similarly, the increasing tree of u, denoted IncT(u), is defined as follows:
if n is the minimum symbol that appears in u, so that u = tnt′ , then IncT(u)

14

ALAN J. CAIN AND ANTÓNIO MALHEIRO

has root labelled by n, and the left subtree of its root is IncT(t) and the
right subtree of the root is IncT(t′ ). That is,

IncT(u) = IncT tnt′ =

n

IncT(t′ )

IncT(t)

Thus if u is 47921013865 (where the underline denotes a single symbol
in A that is not written using a single decimal digit), then IncT(u) and
DecT(u) are respectively the left- and right- hand trees in (4.2).
Remark 4.6. The infix reading of DecT(u) is u and the infix reading of
IncT(u) is u.
Proposition 4.7 ([Gir12, Proposition 4.8]). For any word u ∈ A∗ ,
(1) TRecL (u) = IncT(std(u)−1 );
(2) TRecR (u) = DecT(std(u)−1 );

and TRecL (u), TRecR (u) is a pair of twin binary trees.

(Note that since std(u) is a standard word, it can be viewed as a permutation in one-line notation, and thus its inverse is defined.)
Before proceeding to define the sylvester and Baxter monoids, it is first
necessary to prove two technical lemmata:

Lemma 4.8. Let α, α′ , β, β ′ ∈ A∗ and k ∈ A be such that |α| = |α′ |,
|β| = |β ′ |, the symbol k is greater than every symbol in α, α′ , β, β ′ , and αkβ
and α′ kβ ′ are standard words.
(1) If the decreasing trees DecT(αβ) and DecT(α′ β ′ ) have the same
shape as each other, then the decreasing trees DecT(αkβ) and DecT(α′ kβ ′ )
are of the same shape as each other.
(2) If the increasing trees IncT(αβ) and IncT(α′ β ′ ) have the same shape
as each other, then the increasing trees IncT(αkβ) and IncT(α′ kβ ′ )
are of the same shape as each other.
Proof.

(1) Suppose that the |α|-th symbol in αkβ is c. Now consider
two cases separately:
(a) c is a left child node in DecT(αβ). The infix reading of DecT(αβ)
is αβ, so the left subtree of c must have infix reading α0 , where
α = α0 c, and the right subtree of c must have infix reading β0 ,
where β0 is a prefix of β. Suppose β = β0 β1 ; then β1 is the
infix reading of the part of the tree above and to the right of
c. That is, DecT(αβ) must be as shown in the left-hand side of
(4.7) below.
DecT(αβ)
z
}|
{
β1

(4.7)

z

DecT(αkβ)
}|
{

c
α0

k

c
β0

α0

β1
β0

CRYSTALS AND TREES

15

The tree on the right-hand side of (4.7) has infix reading αkβ.
(Note that in the right-hand tree, the subtree β0 attaches to
the subtree β1 in the same place as c attaches to the subtree
β1 in the left-hand tree.) It is a decreasing tree since k is the
maximum symbol and the relative order of c, α0 , β0 , and β1 is
correct since DecT(αβ) is a decreasing tree. Hence the righthand tree in (4.7) is DecT(αkβ).
Since DecT(α′ β ′ ) has the same shape as DecT(αβ) and |α| =
|α′ |, the |α|-th symbol of α′ β ′ is also a left child and so DecT(α′ β ′ )
has the same shape as the left-hand tree in (4.7). Since k is also
the maximum symbol in α′ kβ ′ , the decreasing tree DecT(α′ kβ ′ )
has the same shape as the right-hand tree in (4.7). Thus DecT(αkβ)
and DecT(α′ kβ ′ ) have the same shape.
(b) c is a right child node or the root node. The infix reading of
DecT(αβ) is αβ, so the left subtree of c must have infix reading
α1 , where α1 c is a suffix of α, and the right subtree of c must
have infix reading β. Suppose α = α0 α1 c; then α0 is the infix
reading of the part of the tree above and to the left of c. That
is, DecT(αβ) must be as shown in the left-hand side of (4.8)
below.

DecT(αβ)
z
}|
{
α0

(4.8)

DecT(αkβ)
}|
{
k

α0

c
α1

z

β
c

β
α1

The tree on the right-hand side of (4.8) has infix reading αkβ. It
is a decreasing tree since k is the maximum symbol and the relative order of c, α0 , α1 , and β is correct since DecT(αβ) is a decreasing tree. Hence the right-hand tree in (4.8) is DecT(αkβ).
Since DecT(α′ β ′ ) has the same shape as DecT(αβ) and |α| =
|α′ |, the |α|-th symbol of α′ β ′ is also a right child or is also
the root node and so DecT(α′ β ′ ) has the same shape as the
left-hand tree in (4.8). Since k is also the maximum symbol in
α′ kβ ′ , the decreasing tree DecT(α′ kβ ′ ) has the same shape as
the right-hand tree in (4.8). Thus DecT(αkβ) and DecT(α′ kβ ′ )
have the same shape.
(2) Since k is greater than every symbol in αβ, the increasing tree
IncT(αkβ) is obtained from IncT(αβ) by adding k as a leaf node.
With the same notation and similar reasoning as in case (1), one
gets the following equivalents of (4.7) (when c is a left child node)

16

ALAN J. CAIN AND ANTÓNIO MALHEIRO

and (4.8) (when c is a right child node or the root node):
z

IncT(αβ)
}|
{

z

β1

IncT(αkβ)
}|
{

c
α0

β1

c
α0

β0

β0
k

z

IncT(αβ)
}|
{
α0

z

IncT(αkβ)
}|
{
α0

c
α1

c
β

α1

β
k

In each case, the right-hand tree is an increasing tree with infix read
αkβ, by the fact that k is the maximum symbol and the relative
order of c, α0 , α1 , and β is correct since IncT(αβ) is an increasing
tree. Hence in both cases the right-hand tree is IncT(αkβ). Thus,
by similar reasoning to case (1), IncT(αkβ) and IncT(α′ kβ ′ ) have
the same shape.

The second technical lemma is simply the dual of the first:
Lemma 4.9. Let α, α′ , β, β ′ ∈ A∗ be such that |α| = |α′ |, |β| = |β ′ |, and
α1β and α′ 1β ′ are standard words.
(1) If the decreasing trees DecT(αβ) and DecT(α′ β ′ ) have the same
shape as each other, then the decreasing trees DecT(α1β) and DecT(α′ 1β ′ )
are of the same shape as each other.
(2) If the increasing trees IncT(αβ) and IncT(α′ β ′ ) have the same shape
as each other, then the increasing trees IncT(α1β) and IncT(α′ 1β ′ )
are of the same shape as each other.
Equipped with these notions of binary search trees and insertion algorithms, it is now possible to use them to define the sylvester and Baxter
monoids (approach 2 in the introduction).
4.2. Sylvester monoid. Define the sylvester P-symbol of u ∈ A∗ by Psylv (u) =
TR (u), and the sylvester Q-symbol of u ∈ A∗ by Qsylv (u) = TRecR (u). The
definition of the relation ≡sylv using right strict binary search trees and insertion is:
u ≡sylv v ⇐⇒ Psylv (u) = Psylv (v).
Using this definition, it can be shown that ≡sylv is a congruence on A∗ ,
which is known as the sylvester congruence. The factor monoid A∗ /≡sylv is
the sylvester monoid and is denoted sylv. The congruence ≡sylv naturally

CRYSTALS AND TREES

17

restricts to a congruence on A∗n , and the factor monoid A∗n / ≡sylv is the
sylvester monoid of rank n and is denoted sylvn .
The monoid sylv is presented by hA | Rsylv i, where

Rsylv = (cavb, acvb) : a ≤ b < c, v ∈ A∗ ;

the monoid sylvn is presented by hAn | Rsylv i, where the set of defining relations Rsylv is naturally restricted to A∗n × A∗n . Notice that sylv and sylvn are
multihomogeneous. (See [CGM17] for a general discussion of homogeneous
and multihomogeneous monoids.)

It is straightforward to see that the map u 7→ Psylv (u), Qsylv (u) is a
bijection between words in A∗ and pairs consisting of a right strict binary
search tree and a decreasing tree of the same shape; this is the sylvester analogue of the Robinson–Schensted correspondence. For instance, if Psylv (u)
and Qsylv (u) are the right-hand trees in (4.1) and (4.2) respectively, then
u = 5451761524.
For any word u ∈ A∗ , the set of words in the ≡sylv -class of u is the
sylvester class of u. Extend this terminology to right strict binary search
trees: for such a tree T , the set of words w ∈ A∗ such that Psylv (w) = T
is the sylvester class of T . The left-to-right postfix reading Post(T ) is an
element of the sylvester class of T : that is, Psylv (Post(T )) = T . (Note that
the infix reading In(T ) is not in general an element of the sylvester class
of T .) The following lemma follows immediately from the definition of the
left-to-right postfix reading:
Lemma 4.10. Let T be an unlabelled binary tree. Under the sylvester analogue of the Robinson–Schensted correspondence, the set of postfix readings
of right strict binary search trees of shape T is obtained by fixing a particular
sylvester Q-symbol of shape T and varying the sylvester P-symbol of over all
right strict binary search trees of shape T .
The following corollary of Proposition 4.7 does not seem to have been
stated before:
Corollary 4.11. For u, v ∈ A∗ ,
u ≡sylv v ⇐⇒ wt(u) = wt(v)


∧ Sh DecT(std(u)−1 ) = Sh DecT(std(v)−1 ) .

Proof. Suppose that u ≡sylv v. Then TR (u) = TR (v). Thus wt(u) =
wt(TR (u)) = wt(TR (v)) = wt(v) and, by Proposition 4.7,

Sh DecT(std(u)−1 ) = Sh(Qsylv (u)) = Sh(Psylv (u))

= Sh(Psylv (v)) = Sh(Qsylv (v)) = Sh DecT(std(v)−1 ) .

On the other hand, suppose wt(u) = wt(v) and Sh DecT(std(u)−1 ) =

Sh DecT(std(v)−1 ) . Then

Sh(Psylv (v)) = Sh(Qsylv (v)) = Sh DecT(std(v)−1 )

= Sh DecT(std(u)−1 ) = Sh(Qsylv (u)) = Sh(Psylv (u)).
Thus Psylv (u) and Psylv (v) have the same shape. Since wt(u) = wt(v), the
trees Psylv (u) and Psylv (v) have the same content. By Proposition 4.1, the

18

ALAN J. CAIN AND ANTÓNIO MALHEIRO

infix reading of a binary search tree is the unique weakly increasing word
with the same content, and so it follows that the infix readings of Psylv (u)
and Psylv (v) are equal. Since Psylv (u) and Psylv (v) have the same shape, they
are thus identical. Hence u ≡sylv v.

4.3. Baxter monoid. The definition of the relation ≡baxt uses pairs of twin
binary search trees. For any word u ∈ A∗ , the binary search trees TL (u)
and TR (u) form a pair of twin binary search
trees. Define the Baxter Q
symbol of u by Pbaxt (u) = TL (u), TR (u) , and the Baxter Q-symbol of u by
Qbaxt (u) = TRecL (u), TRecR (u) . Define ≡baxt by:
u ≡baxt v ⇐⇒ Pbaxt (u) = Pbaxt (v).

Using this definition, it follows that ≡baxt is a congruence on A∗ , which is
known as the Baxter congruence. The factor monoid A∗ /≡baxt is the Baxter
monoid and is denoted baxt. The congruence ≡baxt naturally restricts to a
congruence on A∗n , and the factor monoid A∗n / ≡baxt is the Baxter monoid
of rank n and is denoted baxtn .
The monoid baxt is presented by hA | Rbaxt i, where

Rbaxt = (cudavb, cuadvb) : a ≤ b < c ≤ d, u, v ∈ A∗
∪ { (budavc, buadvc) : a < b ≤ c < d, u, v ∈ A∗ };

the monoid baxtn is presented by hAn | Rbaxt i, where the set of defining
relations Rbaxt is naturally restricted to A∗n × A∗n . Note that baxt and baxtn
are multihomogeneous.
The map
 


u 7→ Pbaxt (u), Qbaxt (u) = TL (u), TR (u) , TRecL (u), TRecR (u)

is a bijection between words in A∗ and pairs consisting of a pair of twin
binary search tree and a pair made up of an increasing and a decreasing
tree of the same shape as the corresponding binary search trees; this is the
Baxter analogue of the Robinson–Schensted correspondence. For instance,
if Pbaxt (u) is the pair of twin binary search trees in (4.1), and Qbaxt (u) is the
pair of increasing and decreasing trees in (4.2), then u = 5451761524.
For example, if u = 5451761524, then std(u) = 64711092835, so (std(u))−1 =
47921013865. Hence TRecL (u) and IncT((std(l))−1 ) are both the left-hand
tree in (4.2), and TRecR (u) and DecT((std(u))−1 ) are both the right-hand
tree in (4.2).
For any word u ∈ A∗ , the set of words in the ≡baxt -class of u is the Baxter
class of u. Extend this terminology to pairs of twin binary search trees: for
such a pair (TL , TR ), the set of words w ∈ A∗ such that Pbaxt (w) = T is the
Baxter class of T .
There is a straightforward method for computing words in the Baxter
class of a pair of twin binary search trees (TL , TR ):
Method 4.12. Input: A pair of twin binary search trees (TL , TR ).
Output: A word in the Baxter class of (TL , TR ).
(1) Set (UL , UR ) to be (TL , TR ). (Throughout this computation, UL is a
forest of left strict binary search trees and UR is a right strict binary
search tree.)

CRYSTALS AND TREES

19

(2) If UL and UR are empty, halt.
(3) Given some (UL , UR ), choose and output some symbol a that labels
a root of some tree in the forest UL and a leaf of the tree UR .
(4) Delete the corresponding root vertex of UL and the corresponding
leaf vertex of UL .
(5) Go to step 2.
This is essentially [Gir12, Algorithm on p.133], except that the method
given here is non-deterministic in that there may be several choices for a in
step 3. As these choices vary, all words in the Baxter class of (TL , TR ) are
obtained. If, in step 3, one always chooses the leftmost possible a, call the
resulting word the left-consistent reading of (TL , TR ). (By [Gir12, Proposition 4.16], the left-consistent reading of (TL , TR ) is the lexicographically
smallest word in the corresponding Baxter class.) The following lemma
follows immediately from the definition of the left-consistent reading:
Lemma 4.13. Let (TL , TR ) be a pair of twin binary trees. Under the Baxter
analogue of the Robinson–Schensted correspondence, the set of left-consistent
readings of pairs of twin binary search trees of shape (TL , TR ) is obtained by
fixing a particular Baxter Q-symbol of shape (TL , TR ) and varying the Baxter
P-symbol over all pairs of twin binary search trees of shape (TL , TR ).
The following result is the analogy of Corollary 4.11 for the Baxter monoid:
Corollary 4.14. For u, v ∈ A∗ ,
u ≡baxt v ⇐⇒ wt(u) = wt(v)


∧ Sh DecT(std(u)−1 ) = Sh DecT(std(v)−1 )


∧ Sh IncT(std(u)−1 ) = Sh IncT(std(v)−1 ) .

Proof. Follow the reasoning in the proof of Corollary 4.11, but working additionally with TL (·), TRecL (·), and IncT(std(·)−1 ).

5. Quasi-crystals with abstract shapes
An abstract shape is a map σ : A∗ → S satisfying the following axioms:
S1 The map σ is invariant under standardization, in the sense that for
all u ∈ A∗ σ(u) = σ(std(u)).
S2 For all u, v ∈ A∗ and a ∈ A, if wt(u) = wt(v) and σ(u) = σ(v), then
σ(ua) = σ(va) and σ(au) = σ(av) for all w ∈ A∗ .
Explicit examples of shapes will be given in the next section. For the moment, note that by Proposition 3.6 and Corollary 3.10, axiom S1 is equivalent to saying that σ is invariant under the quasi-Kashiwara operators,
in the sense that for all u ∈ A∗ and all i ∈ N, if ëi (u) is defined, then
σ(u) = σ(ëi (u)), and if f¨i (u) is defined, σ(u) = σ(f¨i (u)). Thus, if axiom S1
is satisfied, every element of a given connected component of Γ(hypo) will
have the same image under σ.
For u, v ∈ A∗ , a quasi-crystal isomorphism θ : Γ(hypo, u) → Γ(hypo, v) is
shape-preserving (with respect to an abstract shape σ) if σ(w) = σ(θw) for
all w ∈ Γ(hypo, u).

20

ALAN J. CAIN AND ANTÓNIO MALHEIRO

Define a relation ∼σ on the free monoid A∗ as follows: u ∼σ v if and only
if there is a shape-preserving quasi-crystal isomorphism θ : Γ(hypo, u) →
Γ(hypo, v) such that θ(u) = v. That is, u ∼σ v if and only if u and v
have the same image under σ and are in the same position in isomorphic
connected components of Γ(hypo). Note that ∼σ ⊆ ∼.
Proposition 5.1. The relation ∼σ is a congruence on the free monoid A∗ .
Proof. It is clear from the definition that ∼σ is an equivalence relation; it
thus remains to prove that ∼σ is compatible with multiplication in A∗ .
Suppose u ∼σ v and w ∈ A∗ . Suppose w = w1 · · · wk (where wi ∈ A).
The aim is to proceed by induction on i and show there is a shape-preserving
quasi-crystal isomorphism θi : Γ(hypo, uw1 · · · wi ) → Γ(hypo, vw1 · · · wi ) such
that θ(uw1 · · · wi ) = vw1 · · · wi for all i ∈ {0, 1, . . . , k} (formally taking
w1 · · · wi to be ε when i = 0).
For i = 0, since u ∼σ v, there is by definition a shape-preserving quasicrystal isomorphisms θ0 : Γ(hypo, u) → Γ(hypo, v) such that θ(u) = v. This
is the basis of the induction.
So assume there is a shape-preserving quasi-crystal isomorphism θi :
Γ(hypo, uw1 · · · wi ) → Γ(hypo, vw1 · · · wi ) such that θi (uw1 · · · wi ) = vw1 · · · wi .
In particular, uw1 · · · wi ∼ vw1 · · · wi . Since ∼ is a congruence, uw1 · · · wi wi+1 ∼
vw1 · · · wi wi+1 , and so there is a quasi-crystal isomorphism (which is not yet
known to be shape-preserving) θi+1 : Γ(hypo, uw1 · · · wi+1 ) → Γ(hypo, vw1 · · · wi+1 )
such that θi+1 (uw1 · · · wi+1 ) = vw1 · · · wi+1 . Furthermore, since θi is shapepreserving, σ(uw1 · · · wi ) = σ(θ(uw1 · · · wi )) = σ(vw1 · · · wi ). Combine this
with uw1 · · · wi ∼ vw1 · · · wi and use axiom S2 to see that σ(uw1 · · · wi+1 ) =
σ(vw1 · · · wi+1 ). Thus, by axiom S1, every element in the connected components Γ(hypo, uw1 · · · wi+1 ) and Γ(hypo, vw1 · · · wi+1 ) have the same shape.
Hence θi+1 is shape-preserving.
Hence, by induction, θk : Γ(hypo, uw) → Γ(hypo, vw) is a shape-preserving
quasi-crystal isomorphism; therefore uw ∼σ vw.
Similar reasoning shows that wu ∼σ wv; hence ∼σ is compatible with
multiplication and is thus a congruence.

Thus every abstract shape σ gives rise to a monoid A∗ /∼σ .
6. Crystallizing the sylvester monoid
6.1. Definition by crystals. Let S be the set of unlabelled binary trees
and define σsylv (u) = Sh(DecT(std(u)−1 )) for all u ∈ A∗ .
Proposition 6.1. σsylv is an abstract shape.
Proof. By Proposition 3.6, the map σsylv is invariant under the quasi-Kashiwara
operators, and so satisfies axiom S1.
To see that σsylv satisfies S2, proceed as follows. Let u, v ∈ A∗ be such
that u ∼ v and σsylv (u) = σsylv (v), and let a ∈ A.
The first aim is to prove that σsylv (ua) = σsylv (va). When one computes
std(ua) and std(va), the symbol a is replaced by the same symbol b in both
words, since u and v have the same content. Let k = |u| + 1. In std(ua)
(viewed as a permutation), k is mapped to b. Thus, k is the b-th symbol, and
the maximum symbol, in both std(ua)−1 and std(va)−1 . That is, std(u)−1 =

CRYSTALS AND TREES

21

αβ, std(ua)−1 = αkβ, std(v)−1 = α′ β ′ and std(va)−1 = α′ kβ ′ for some
α, α′ , β, β ′ ∈ A∗ , such that |α| = |α′ |, |β| = |β ′ |, the symbol k is greater than
every symbol in α, α′ , β, β ′ , and αkβ and α′ kβ ′ are standard words. Furthermore, DecT(std(u)−1 ) = DecT(αβ) and DecT(std(v)−1 ) = DecT(α′ β ′ )
have the same shape, since σsylv (u) = σsylv (v). Thus, by Lemma 4.8(1),
DecT(std(ua)−1 ) = DecT(αkβ) and DecT(std(va)−1 ) = DecT(α′ kβ ′ ) have
the same shape. Hence σsylv (ua) = σsylv (va).
The next aim is to prove that σsylv (au) = σsylv (av). When one computes
std(au) and std(av), the symbol a is replaced by the same symbol b in
both words, since u and v have the same content. In std(au) (viewed as
a permutation), 1 is mapped to b. Thus, 1 is the b-th symbol, and the
minimum symbol, in both std(au)−1 and std(av)−1 . By similar reasoning
to the above, but using Lemma 4.9(1), one sees that DecT(std(au)−1 ) and
DecT(std(av)−1 ) have the same shape. Hence σsylv (au) = σsylv (av).

As a consequence of Proposition 6.1, one can define a relation ∼sylv on
the free monoid A∗ to be the relation ∼σ from Section 5 with the abstract
shape σ = σsylv . By Propositions 5.1 and 6.1, ∼sylv is a congruence.
When viewing the quasi-crystal graph Γ(hypo) in the context of σsylv preserving isomorphisms, denote it by Γ(sylv). Similarly, denote the connected component Γ(hypo, u) by Γ(sylv, u). (This is arguably an abuse of
notation, since Γ(hypo) and Γ(sylv) are the same graph, and the difference
is in the notion of isomorphism and the relation to which it gives rise.)
Proposition 6.2. The relations ∼sylv and ≡sylv coincide.
Proof. Let u, v ∈ A∗ . Suppose that u ∼sylv v. Then u ∼ v and hence
wt(u) = wt(v). Furthermore, σsylv (u) = σsylv (v), and so


Sh DecT(std(u)−1 ) = σsylv (u) = σsylv (v) = Sh DecT(std(v)−1 ) .

Hence, by Corollary 4.11, u ≡sylv v.
Now suppose that u ≡sylv v. Then u ≡hypo v and so u ∼ v and so there is
a quasi-crystal isomorphism θ : Γ(hypo, u) → Γ(hypo, v) with θ(u) = v. By
Corollary 4.11,


σsylv (u) = Sh DecT(std(u)−1 ) = Sh DecT(std(v)−1 ) = σsylv (v).

Thus, by S2, σsylv (θ(w)) = σsylv (w) for all w ∈ Γ(hypo, u). Hence θ is a
σsylv -preserving quasi-crystal isomorphism and so u ∼sylv v.

Our aim here has been to show that ≡sylv can be defined using quasicrystals; thus we have avoided using the prior knowledge that ≡sylv is a
congruence [HNT05]. If we had used that result, it would have been straightforward to recover the fact that σsylv is an abstract shape.
6.2. Characterizing highest-weight elements.

Proposition 6.3. Let T be an unlabelled binary tree. The set of words in
A∗ that are postfix readings of right strict binary search trees of shape T
form a single connected component of Γ(sylv).
Proof. Suppose u and v are postfix readings of two right strict binary search
trees of shape T . Then std(u) and std(v) are also postfix readings of two

22

z

ALAN J. CAIN AND ANTÓNIO MALHEIRO

1

1

2
2

Γ(sylv, 1221)
}|

{

z

2121

Γ(sylv, 2121)
}|

{

z

2
1

1

2

Γ(sylv, 1212)
}|

{

2
1
1
2
1

1
4

1

2

3

1

1
5

1

2

2
4

3

|

{z

1

3
3

4

1

3

}

2151

|

3141

4

2

1

2

3

1
2

1

3

1

3

{z

3

1

3

3231

}

1

1

2
4

3131
2

2
Legend

1

2141

3

4
1

1

2

3
1

3

2131

3

5

4

1
1

2

1

|

2
3

{z

1

4

3

1

4

3

1

2

5

Figure 4. Part of the connected components Γ(sylv, 1221)
and Γ(sylv, 2121), which are linked by a shape-preserving
isomorphism, and part of the connected component
Γ(sylv, 1212), which is only isomorphic to the others as a
labelled digraph.
binary search trees of shape T [HNT05, Lemma 11]. Since there is exactly
one right strict binary search of a given shape labelled by a standard word
[HNT05, Note 3], it follows that std(u) = std(v) and so u and v are in the
same connected component of Γ(sylv) by Corollary 3.10.

Lemma 6.4. Let u ∈ A∗ and i ∈ N. Then ëi (u) is defined if and only if
TR (u) contains at least one node i + 1, but does not contain a node i + 1 in
the right subtree of the topmost node i.
Proof. By definition, ëi (u) is defined if and only if every symbol i + 1 is to
the right of every symbol i in u. In terms of Algorithm 4.5, this is equivalent
to every symbol i + 1 being inserted before every symbol i, which in turn
is equivalent to no symbol i + 1 being inserted into the right subtree of the
topmost symbol i.

Proposition 6.5. Let u ∈ A∗ . Then u is a highest-weight word if and only
if TR (u) has the following property: if the right interval partition of TR (u)
has ℓ parts, then for a ∈ {1, . . . , ℓ} ⊆ A, the nodes in the a-th right interval
are labelled by a.

3

}

CRYSTALS AND TREES

23

Before proceeding to the proof, an example is helpful. The word u =
1121335432 is highest weight, and TR (u) is
2
1
1
1

3
2

3
3

,
4
5

which satisfies the condition in Proposition 6.5. On the other hand, the word
u = 5451761524 does not have highest weight, and TR (u) is the right-hand
tree in (4.1), which does not satisfy the condition.
Proof. Suppose u is a highest-weight word. Then ëi (u) is undefined for all
i. Let ℓ be the number of right intervals of TR (u). Since the infix reading of
TR (u) is a weakly increasing word that must increase immediately after the
rightmost nodes in the first ℓ − 1 right intervals, there are at least ℓ distinct
symbols among the labels in TR (u).
If i > 1 is a symbol in u, then i − 1 is also a symbol in u, for otherwise
ëi−1 (u) would be defined. Consequently, u contains the symbols 1, . . . , m
for some m ≥ ℓ. If m > 1, then, by Lemma 6.4, there is a symbol 2 in the
right subtree of the topmost symbol 1. Thus the symbols 1 must label all
nodes in the first right interval of TR (u). Proceeding inductively and using
Lemma 6.4, one sees that a must label all nodes in the a-th right interval.
Hence TR (u) has the form described in the statement.
Now suppose that TR (u) has the form described. It is immediate that
a + 1 is in the right subtree of the topmost node a for all a ∈ {1, . . . , ℓ},
and so ëi (u) is undefined for i ≤ ℓ. Since ℓ + 1 is the maximum symbol in
TR (u), it follows that ëi (u) is undefined for all i by Lemma 6.4, and so u
has highest weight.

Note that it would be possible to prove Proposition 6.5 by appealing to the
corresponding result for the hypoplactic monoid and quasi-ribbon tableaux
[CM17, Proposition 6(2)] to characterize highest weight words, but it seems
clearer to give a direct proof that reasons only about trees.
6.3. The sylvester version of the Robinson–Schensted correspondence. The following result clarifies the interaction of the quasi-crystal
structure and the sylvester version of the Robinson–Schensted correspondence:
Proposition 6.6. Let u, v ∈ A∗ . The words u and v lie in the same connected component of Γ(sylv) if and only if Qsylv (u) = Qsylv (v).
Proof. Suppose Qsylv (u) = Qsylv (v). Hence TRecR (u) = TRecR (v) and by
Proposition 4.7, DecT(std(u)−1 ) = DecT(std(u)−1 ). Thus, by Proposition 4.1,
std(u)−1 and std(v)−1 are the infix readings of the same labelled binary tree,
and so std(u) = std(v). Since u and std(u) lie in the same connected component of Γ(sylv) by Corollary 3.10, and similarly for v and std(v), it follows
that u and v are in the same connected component of Γ(sylv).
On the other hand, if u and v lie in the same connected component of
Γ(sylv), then std(u) = std(v) by Corollary 3.10 and so Qsylv (u) = Qsylv (v).


24

ALAN J. CAIN AND ANTÓNIO MALHEIRO

Thus the sylvester Q-symbol indexes connected components of the quasicrystal graph and the sylvester P-symbol locates a word within that component. Note that combining Proposition 6.6 and Lemma 4.10, one recovers
Proposition 6.3.
The Knuth ‘hook-length’ formula
Q shows that the number of descending
trees of the same shape as T is n!/ v∈T hv , where hv is the number of nodes
in the subtree rooted at v [Knu98, § 5.1.4, Exer. 20]. This gives a formula
for the number of sylvester Q-symbols of a given shape, and thus for the
size of sylvester classes corresponding to left strict binary search trees of a
given shape, and thus for the number of quasi-crystal components that are
mapped to a given one by a σsylv -preserving quasi-crystal isomorphism.
In the infinite-rank setting, there are infinitely many sylvester P-symbols
of a given shape. On restricting to the rank n case, the number of sylvester
P-symbols of a given shape can be calculated using the same formula as for
the hypoplactic monoid [CM17, Theorem 4]:
Proposition 6.7. Let T be a binary search tree for which the right interval
partition has ℓ parts. The number of right strict binary search trees of shape
T labelled by symbols from An is
(
n+|T |−ℓ
if ℓ ≤ n
n−ℓ
0
if ℓ > n.
Proof. Consider a highest-weight word u ∈ A∗n such that TR (u) has shape
T . By Proposition 6.5, u contains the symbols {1, . . . , ℓ}. Let α be the
shape of the quasi-ribbon tableau Phypo (u). Since u is also a highest-weight
word in Γ(sylv) and thus in Γ(hypo), it follows that the column reading v of
Phypo (u) is also a highest weight word in Γ(hypo) and so α = wt(v) = wt(u)
[CM17, Proposition 6]. In particular, ℓ(α) = ℓ and |α| = |v| = |u| = |T |.
Since Γ(sylv, u) = Γ(hypo, u) is isomorphic to Γ(hypo, v), they both contain the same number of words that lie in A∗n , and so the result follows by
subsituting the given values for ℓ(α) and |α| into [CM17, Theorem 4].

6.4. Counting factorizations. One interpretation of the Littlewood–Richardson
rule [Ful97, ch. 5] is that the Littlewood–Richardson coefficients cνλµ are 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, and is rather
dependent only on the shape. The quasi-crystal structure yields a similar
result for hypo [CM17, Theorem 5], and a minimal modification to the proof
gives the similar result for the sylvester monoid:
Theorem 6.8. The number of distinct factorizations of an element of the
sylvester monoid corresponding to a right strict binary search tree of shape
T into elements that correspond to right strict binary search trees of shapes
U and V is dependent only of T , U , and V , and not on the content of the
element.
Proof. For the purposes of this proof, a word u ∈ A∗ is a postfix word if it
is the postfix reading of a binary search tree; a postfix word u has shape U ,

CRYSTALS AND TREES

25

where U is an unlabelled binary tree, if it is the postfix reading of a binary
search tree of shape U .
Let T , U , and V be unlabelled binary trees. Let w ∈ A∗ be a postfix
word of shape T . Let

w
SU,V
= (u, v) : u, v ∈ A∗n are postfix words,
u has shape U ,
v has shape V ,
w ≡sylv uv .
w
SU,V

So
is a complete list of factorizations of w into elements whose corresponding right strict binary search trees have shapes U and V . Let i ∈ N
w . Then w ≡
and suppose ëi (w) is defined. Pick some pair (u, v) ∈ SU,V
sylv uv
and so ëi (uv) is defined, and ëi (w) = ëi (uv). By [CM17, Lemma 2], either
ëi (w)
,
ëi (uv) = uëi (v), or ëi (uv) = ëi (u)v. In the former case, (u, ëi (v)) ∈ SU,V
ë (w)

i
, since ëi preserves being a postand in the latter case (ëi (u), v) ∈ SU,V
fix word and the shape of the corresponding right strict binary search tree
ëi (w)
w
by Proposition 6.3. So ëi induces an injective map from SU,V
to SU,V
.
ëi (w)
w
¨
to S . Hence
It follows that fi induces the inverse map from S

U,V

U,V

w | = |S f¨i (w) |. Since
Similarly, if f¨i (w) is defined, then |SU,V
=
U,V
all the postfix words whose corresponding binary search trees have shape T
lie in the same connected component of Γ(sylv) by Proposition 6.3, it follows
w | is dependent only on T , not on w.
that |SU,V

w |
|SU,V

ëi (w)
|.
|SU,V

6.5. Satisfying an identity. Another application of the quasi-crystal structure was to prove that the hypoplactic monoid satisfies a non-trivial identity
[CM17, Theorem 6]. Similarly, it is possible to use the quasi-crystal structure to prove that the sylvester monoid satisfies an identity.
Theorem 6.9. The sylvester monoid satisfies the identity xyxy = yxxy.
Proof. Let x, y ∈ A∗ . The proof that xyxy = yxxy 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 ∈ N. So xyxy must contain a subsequence
(i+1)i for all i ∈ {1, . . . , ℓ−1}, where ℓ is the maximum symbol appearing in
x or y. The symbols i + 1 and i may each lie in x or y, but in any case, there
is a subsequence (i + 1)i in yxxy. Hence ëi (yxxy) is undefined for all i ∈ N
and so yxyx is also highest-weight. Clearly wt(xyxy) = wt(yxxy). Consider
applying Algorithm 4.5 to xyxy and yxxy. In both cases, the algorithm
initially computes TR (xy). At this point, every symbol in B = {1, . . . , ℓ}
appears in the tree and so the infix reading of TR (xy) contains all these
symbols. Thus any symbol b ∈ B that is subsequently inserted will be
placed either as the left child of a node b that is already present, or into the
right subtree of the topmost node b − 1 that is already present. Thus the
trees TR (xyxy) and TR (yxxy) are identical.
The remaining reasoning parallels the proof of [CM17, Theorem 6]. For
the induction step, suppose xyxy is not highest-weight, and that x′ y ′ x′ y ′ ≡sylv
y ′ x′ x′ y ′ for all x′ , y ′ ∈ A∗ such that x′ y ′ x′ y ′ has higher weight than xyxy.

26

ALAN J. CAIN AND ANTÓNIO MALHEIRO

Then ëi (xyxy) is defined for some i ∈ N. Neither x nor y contains a symbol
i, since otherwise there would be a subsequence (i + 1)i. So ǫ̈i (xyxy) =
ǫ̈i (yxxy) = |xyxy|i+1 = |yxxy|i+1 = 2|x|i+1 + 2|y|i+1 = 2ǫ̈i (x) + 2ǫ̈i (y),
and ǫ̈i (xyxy) applications of ëi change every symbol i + 1 in xyxy to i.
ǫ̈ (xyxy)
ǫ̈ (yxxy)
That is, ëi i
(xyxy) and ëi i
(yxxy) are both defined and are equal
ǫ̈ (x)
ǫ̈ (y)
′
′
′
′
′
′
′
′
to x y x y and y x x y respectively, where x′ = ëi i (x) and y ′ = ëi i (y).
Since x′ y ′ x′ y ′ has higher weight than xyxy, it follows by the induction hypothesis that x′ y ′ x′ y ′ ≡sylv y ′ x′ x′ y ′ . Hence
ǫ̈ (xyxy) ′ ′ ′ ′
ǫ̈ (xyxy) ′ ′ ′ ′
xyxy = f¨i i
(x y x y ) ≡sylv f¨i i
(y x x y ) = yxxy.

This completes the induction step and thus the proof.



For an alternative proof of Theorem 6.9 that does not require the quasicrystal structure, see [CM, Section 3.3].
7. Crystallizing the Baxter monoid
7.1. Definition by crystals. Let S be the set of pairs of twin binary trees
and define σbaxt (u) = Sh(IncT(std(u)−1 )), Sh(DecT(std(u)−1 )) for all u ∈
A∗ .
Proposition 7.1. σbaxt is an abstract shape.
Proof. By Proposition 3.6, the map σbaxt is invariant under the quasi-Kashiwara
operators, and so satisfies axiom S1.
To see that σbaxt satisfies S2, proceed as follows. Let u, v ∈ A∗ be such
that wt(u) = wt(v) and σbaxt (u) = σbaxt (v), and let a ∈ A.
Then Sh(IncT(std(u)−1 )) = Sh(IncT(std(v)−1 )) and Sh(DecT(std(u)−1 )) =
Sh(DecT(std(v)−1 )). By the reasoning in the proof of Proposition 6.1, Sh(DecT(std(ua)−1 )) =
Sh(DecT(std(va)−1 )) and Sh(DecT(std(au)−1 )) = Sh(DecT(std(av)−1 )). Symmetrical reasoning, but using part (2) of Lemmata 4.8 and 4.9 shows that
Sh(IncT(std(ua)−1 )) = Sh(IncT(std(va)−1 )) and Sh(IncT(std(au)−1 )) =
Sh(IncT(std(av)−1 )). Hence σbaxt (ua) = σbaxt (va) and σbaxt (au) = σbaxt (av).
Hence σbaxt satisfies S2.

As a consequence of Proposition 7.1, one can define a relation ∼baxt on
the free monoid A∗ to be the relation ∼σ from Section 5 with the abstract
shape σ = σbaxt . By Propositions 5.1 and 7.1, ∼baxt is a congruence.
When viewing the quasi-crystal graph Γ(hypo) in the context of σbaxt preserving isomorphisms, denote it by Γ(baxt). Similarly, denote the connected component Γ(hypo, u) by Γ(baxt, u). (This is arguably an abuse of
notation, since Γ(hypo) and Γ(baxt) are the same graph, and the difference
is in the notion of isomorphism and the relation to which it gives rise.)
Proposition 7.2. The relations ∼baxt and ≡baxt coincide.
Proof. Let u, v ∈ A∗ . Suppose that u ∼baxt v. Then u ∼ v and hence
wt(u) = wt(v). Furthermore, σbaxt (u) = σbaxt (v), and so

Sh(IncT(std(u)−1 )), Sh(DecT(std(u)−1 )) = σbaxt (u)

= σbaxt (v) = Sh(IncT(std(v)−1 )), Sh(DecT(std(v)−1 ))

CRYSTALS AND TREES

27

Hence, by Corollary 4.14, u ≡baxt v.
Now suppose that u ≡baxt v. Then u ≡hypo v and so u ∼ v and so there is
a quasi-crystal isomorphism θ : Γ(hypo, u) → Γ(hypo, v). By Corollary 4.14,

σbaxt (u) = Sh(IncT(std(u)−1 )), Sh(DecT(std(u)−1 ))

= Sh(IncT(std(v)−1 )), Sh(DecT(std(v)−1 )) = σbaxt (v).

Thus, by S2, σbaxt (θ(w)) = σbaxt (w) for all w ∈ Γ(hypo, u). Hence θ is a
σbaxt -preserving quasi-crystal isomorphism and so u ∼baxt v.

As was the case for ≡sylv , our aim here has been to show that ≡baxt
can be defined using quasi-crystals; thus we have avoided using the prior
knowledge that ≡baxt is a congruence [Gir12], from which, it would have
been straightforward to recover the fact that σbaxt is an abstract shape.
7.2. Characterizing highest weight elements.
Proposition 7.3. Let (TL , TR ) be a pair of twin binary trees. The set of
words in A∗ that are left-consistent readings of pairs of twin binary search
trees of shape (TL , TR ) form a single connected component of Γ(baxt).

Proof. Suppose u and v are left-consistent readings of two pairs of twin
binary seach trees of shape (TL , TR ). Then std(u) and std(v) are also leftconsistent readings of shape (TL , TR ) (by [HNT05, Lemma 11] and its dual).
Since there is exactly one pair of twin binary search trees of a given shape
labelled by a standard word (by [HNT05, Note 3] and its dual), it follows
that std(u) = std(v) and so u and v are in the same connected component
of Γ(baxt) by Corollary 3.10.

The following lemma is the dual of Lemma 6.4, and can be proved by a
dual argument.
Lemma 7.4. Let u ∈ A∗ and i ∈ N. Then ëi (u) is defined if and only if
TL (u) contains at least one node i + 1, but does not contain a node i in the
left subtree of the topmost node i + 1.
The following result follows from the argument in the proof of Proposition 6.5
plus a dual argument:
Proposition 7.5. Let u ∈ A∗ . Then u is a highest-weight word if and only
if Pbaxt (u) = (TL (u), TR (u)) has the following properties:
• if the left interval partition of TL (u) has k parts, then for a ∈
{1, . . . , k} ⊆ A, the nodes in the a-th left interval are labelled by
a;
• if the right interval partition of TR (u) has ℓ parts, then for a ∈
{1, . . . , ℓ} ⊆ A, the nodes in the a-th right interval are labelled by a.
7.3. The Baxter version of the Robinson–Schensted correspondence.
The following result is the parallel of Proposition 6.6 for the Baxter monoid:
Proposition 7.6. Let u, v ∈ A∗ . The words u and v lie in the same connected component of Γ(baxt) if and only if Qbaxt (u) = Qbaxt (v).

28

ALAN J. CAIN AND ANTÓNIO MALHEIRO

Like the case of the sylvester monoid, the Baxter Q-symbol indexes connected components of the quasi-crystal graph and the Baxter P-symbol locates a word within that component.
Unlike the sylvester monoid, there is no known neat formula for the size
of classes of words that represent the same element of the Baxter monoid.
However, the quasi-crystal structure does make it clear that the size of
these classes is dependent only on the shape of the corresponding pair of
twin binary search trees.
Remark 7.7. One might consider trying to use the quasi-crystal structure
to obtain a formula for the size of these classes as follows. By the quasicrystal structure, it suffices to consider the size of the class for a standard
element; that is, for a pair of twin binary search trees (TL , TR ) containing
each symbol in K = {1, . . . , k} exactly once. Each of these binary search
trees can be considered as a partial order on the set K; denote these partial
orders by ≤L and ≤R . Let ≤′L be the dual of ≤L . Now, any reading of
(TL , TR ) can be viewed as a linear order on K that extends ≤′L and ≤R . Since
K is finite, there are finitely many such linear orders, so we can intersect
them to obtain a partial order ⊏. So the readings of (TL , TR ) are in oneto-one correspondence with the linear orders extending ⊏. However, the
problem of the number of linear orders extending a given partial order is
#P -complete [BW91].
Of course, not all partial orders on K will arise as ⊏, so it is possible that
a more refined version of this argument, using the structure of the pair of
twin binary search trees to gain information about ⊏, might still work.
7.4. Counting factorizations. The following result is the parallel of Theorem 6.8
for the Baxter monoid:
Theorem 7.8. The number of distinct factorizations of an element of the
Baxter monoid corresponding to a pair of twin binary search trees of shape
(TL , TR ) into elements that correspond to pairs of twin binary search trees of
shapes (UL , UR ) and (VL , VR ) is dependent only of (TL , TR ), (UL , UR ), and
(VL , VR ), and not on the content of the element.
Proof. For the purposes of this proof, a word u ∈ A∗ is a left-consistent
word if it is the left-consistent reading of a pair of twin binary search tree; a
left-consistent word u has shape (UL , UR ), where (UL , UR ) is a pair of twin
binary trees, if it is the left-consistent reading of a pair of twin binary search
trees of shape (UL , UR ).
Let (TL , TR ), (UL , UR ), and (VL , VR ) be pairs of twin binary trees. Let
w ∈ A∗ be a postfix word such that T is the shape of TR (w). Let

w
S(U
= (u, v) : u, v ∈ A∗n are left-consistent words,
L ,UR ),(VL ,VR )
u has shape (UL , UR ),

v has shape (VL , VR ),
w ≡baxt uv .
Now following the reasoning in the proof of Theorem 6.8, but using Propositions 7.6
w
and 7.3 shows that |S(U
| is dependent only on (TL , TR ), not on
L ,UR ),(VL ,VR )
w.


CRYSTALS AND TREES

29

7.5. Satisfying an identity. The analogy of Theorem 6.9 for the Baxter
monoid is the following:
Theorem 7.9. The Baxter monoid satisfies the identity xyxyxy = xyyxxy.
Proof. Let x, y ∈ A∗ . The proof that xyxyxy = xyyxxy proceeds by reverse
induction on the weight of xyxyxy.
The base case of the induction is when xyxyxy is highest-weight. By reasoning parallel to the proof of Theorem 6.9, xyyxxy is also highest-weight.
Clearly wt(xyxyxy) = wt(xyyxxy). Again by reasoning parallel to the proof
of Theorem 6.9, the trees TR (xyxyxy) and TR (xyyxxy) are equal. By dual
reasoning, the trees TR (xyxyxy) and TR (xyyxxy) are equal.
The induction step is essentially identical to the proof of Theorem 6.9,
except that ǫ̈i (xyxyxy) = 3ǫ̈i (x) + 3ǫ̈i (y) = ǫ̈i (xyyxxy) applications of ëi
change every symbol i + 1 to i. The result follows.

For an alternative proof of Theorem 7.9 that does not require the quasicrystal structure, see [CM, Section 3.5].
8. Perspectives
8.1. The Robinson–Schensted type correspondences. The graphs Γ(hypo),
Γ(sylv) and Γ(baxt) are all the same object; the difference is in the notion of
‘isomorphic’ components. In terms of the hypoplactic, sylvester, and Baxter versions of the Robinson–Schensted correspondence, the Q-symbol of a
word identifies a connected component of the graph, and the P-symbol of
a word identifies its position within that connected component. Viewed in
this context, the sylvester and Baxter Q-symbols are overdetermined. The
‘underlying’ Q-symbol of a word u ∈ A∗ is std(u), which lies in the same
component as u. This corresponds with the notions of ‘compatibility with
the destandardization process’ and std-goodness developed by [Pri13].
8.2. Bases of combinatorial Hopf algebras. In the infinite-rank setting,
there is a very natural connection between the crystal graph Γ(plac) and free
Schur functions. The free Schur functions are indexed by standard Young
tableau and form a basis for the algebra of free symmetric functions FSym.
The crystal graph offers an equivalent way of defining them:
X
ST =
w,
w∈Γ(plac,T )

where Γ(plac, T ) denotes the connected component of Γ(plac) corresponding
to a standard Young tableau T .
Similarly, the free quasi-ribbon functions, which form a basis for FQSym
can be defined with reference to the quasi-crystal graph:
X
Fu =
w,
w∈Γ(hypo,u)

where u ∈ A∗ is a standard word; this follows from the fact that standard
words index connected components of Γ(hypo).

30

ALAN J. CAIN AND ANTÓNIO MALHEIRO

For the basis of the algebra of planar binary trees PBT given by [HNT05,
Eqs (16–17)] (see also [Hiv07, Theorem 27]), the definition using the quasicrystal graph becomes:
X
PT =
w,
w∈Γ(sylv,U )
Sh(U )=T

where T is a binary tree, U ranges over the set of decreasing trees and
Γ(sylv, U ) denotes the connected component of Γ(sylv) indexed by the decreasing tree U .
For the basis of the algebra Baxter given in [Gir12, Theorem 6.12], the
definition using the quasi-crystal graph is:
X
w,
P′ (TL ,TR ) =
w∈Γ(baxt,(UL ,UR ))
Sh(UL ,UR )=(TL ,TR )

where (TL , TR ) is a pair of twin binary trees, (UL , UR ) ranges over the set
of pairs made up of increasing and a decreasing tree with the same infix
reading and Γ(baxt, (UL , UR )) denotes the connected component of Γ(baxt)
indexed by the pair (UL , UR ).
8.3. Speculations. In the quasi-crystal structure for the hypoplactic monoid,
one constructs the graph using the quasi-Kashiwara operators and one defines the congruence using labelled directed graph isomorphisms of connected
components. If one replaces the quasi-Kashiwara operators with the original
Kashiwara operators, one obtains the plactic monoid. On the other hand, if
one requires that labelled directed graph isomorphisms be shape-preserving,
one obtains the sylvester and Baxter monoids. It is thus natural to ask
what monoids arise when one makes both replacements and considers shapepreserving isomorphisms on the graph arising from the original Kashiwara
operators (see Figure 5). (If one uses the abstract notion of shape defined
in Section 5 and the original Kashiware operators, axiom S1 should probably be replaced with ‘invariance under the Kashiwara operators’, which is
a natural analogue in light of the discussion following axioms S1 and S2.
Alternatively, one could seek a natural analogue of standardization for the
original Kashiwara operators.)
References
[BW91]

G. Brightwell & P. Winkler. ‘Counting linear extensions’. Order, 8, no. 3 (1991),
pp. 225–242. doi: 10.1007/BF00383444.
[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.
[CGM17] A. J. Cain, R. D. Gray, & A. Malheiro. ‘On finite complete rewriting systems,
finite derivation type, and automaticity for homogeneous monoids’. Inform. and
Comput., 255, no. 1 (2017), pp. 68–93. doi: 10.1016/j.ic.2017.05.003.
[CM]
A. J. Cain & A. Malheiro. ‘Identities in plactic, hypoplactic, sylvester, Baxter,
and related monoids’. arXiv: 1611.04151.
[CM17] A. J. Cain & A. Malheiro. ‘Crystallizing the hypoplactic monoid: from quasiKashiwara operators to the Robinson–Schensted–Knuth-type correspondence
for quasi-ribbon tableaux’. J. Algebraic Combin., 45, no. 2 (2017), pp. 475–524.
doi: 10.1007/s10801-016-0714-6.

Q
ra
wa
hi
as rs
K to
si- era
ua op

?

Is

om
or

ph
ism
s

31

ra
wa s
hi tor
as a
K p er
o

Sh
a
iso pem pr
o r es
ph er
ism vin
s g

CRYSTALS AND TREES

sylv
baxt

plac

hypo

Figure 5. (Quasi-)-Kashiwara operators, notions of isomorphisms, and monoids.
[Ful97]

W. Fulton. Young Tableaux: With Applications to Representation Theory and
Geometry. No. 35 in LMS Student Texts. Cambridge University Press, 1997.
[Gir12]
S. Giraudo. ‘Algebraic and combinatorial structures on pairs of twin binary
trees’. J. Algebra, 360 (2012), pp. 115–157. doi: 10.1016/j.jalgebra.2012.03.020.
[Gre06] J. Green. Polynomial Representations of GLn. No. 830 in Lecture Notes in Mathematics. Springer, 2nd edition, 2006. doi: 10.1007/3-540-46944-3.
[Hiv00] F. Hivert. ‘Hecke algebras, difference operators, and quasi-symmetric functions’. Advances in Mathematics, 155, no. 2 (2000), pp. 181–238. doi:
10.1006/aima.1999.1901.
[Hiv07] F. Hivert. ‘An Introduction to Combinatorial Hopf Algebras: Examples and
realizations’. In J.-P. Gazeau, J. Nešetřil, & B. Rovan, eds, Physics and Theoretical Computer Science: From Numbers and Languages to (Quantum) Cryptography, no. 7 in NATO Security through Science Series D: Information and
Communication Security. IOS Press, 2007.
[HNT05] F. Hivert, J.-C. Novelli, & J.-Y. Thibon. ‘The algebra of binary search
trees’. Theoret. Comput. Sci., 339, no. 1 (2005), pp. 129–165. doi:
10.1016/j.tcs.2005.01.012.
[Jed11] F. Jedrzejewski. ‘Plactic classification of modes’. In C. Agon, M. Andreatta,
G. Assayag, E. Amiot, J. Bresson, & J. Mandereau, eds, Mathematics and
Computation in Music, no. 6726 in Lecture Notes in Comput. Sci., pp. 350–353.
Springer, 2011. doi: 10.1007/978-3-642-21590-2 31.
[Kas90] 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.
[Kas91] M. Kashiwara. ‘On crystal bases of the q-analogue of universal enveloping
algebras’. Duke Mathematical Journal, 63, no. 2 (1991), pp. 465–516. doi:
10.1215/S0012-7094-91-06321-0.
[KN94] M. Kashiwara & T. Nakashima. ‘Crystal graphs for representations of the qanalogue of classical Lie algebra’. J. Algebra, 165, no. 2 (1994), pp. 295–345.
doi: 10.1006/jabr.1994.1114.
[Knu98] D. E. Knuth. The Art of Computer Programming: Sorting and Searching, vol. 3.
Addison-Wesley, 2nd edition, 1998.

32

[KT97]

[KT99]

[Lot02]
[LS78]
[LS81]

[LS85]

[LS90]

[Mac08]
[Nov00]
[Pri13]

[Sch97]
[Shi05]
[vL01]

ALAN J. CAIN AND ANTÓNIO MALHEIRO

D. Krob & J.-Y. Thibon. ‘Noncommutative Symmetric Functions IV: Quantum
Linear Groups and Hecke Algebras at q = 0’. Journal of Algebraic Combinatorics, 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 )’. Int. J. Algebra Comput., 9, no. 3–4 (1999), pp. 405–430.
doi: 10.1142/S0218196799000254.
M. Lothaire. Algebraic Combinatorics on Words. No. 90 in Encyclopedia of
Mathematics and its Applications. Cambridge University Press, 2002.
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, no. 109 in
Quaderni de ”La Ricerca Scientifica”, pp. 129–156, Rome, 1981. CNR. url:
http://igm.univ-mlv.fr/~ berstel/Mps/Travaux/A/1981-1PlaxiqueNaples.pdf.
A. Lascoux & M.-P. Schützenberger. ‘Schubert polynomials and the LittlewoodRichardson 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. Its. Appl., 23, no. 3 (1990), pp. 223–225. doi:
10.1007/BF01079531.
I. Macdonald. Symmetric Functions and Hall Polynomials. Clarendon Press,
Oxford University Press, 2008.
J.-C. Novelli. ‘On the hypoplactic monoid’. Discrete Mathematics, 217, no. 1–3
(2000), pp. 315–336. doi: 10.1016/S0012-365X(99)00270-8.
J.-B. Priez. ‘A lattice of combinatorial Hopf algebras: Binary trees with multiplicities’. In Formal Power Series and Algebraic Combinatorics, Nancy, 2013.
The Association. Discrete Mathematics & Theoretical Computer Science. url:
http://www.dmtcs.org/pdfpapers/dmAS0196.pdf.
M.-P. Schützenberger. ‘Pour le monoı̈de plaxique’. Mathématiques et sciences
humaines, 140 (1997). url: http://msh.revues.org/2764.
M.
Shimozono.
‘Crystals
for
dummies’,
2005.
Notes.
url:
http://www.aimath.org/WWN/kostka/crysdumb.pdf.
M. A. van Leeuwen. ‘The Littlewood-Richardson Rule, and Related Combinatorics’. In J. R. Stembridge, J.-Y. Thibon, & M. A. van Leeuwen, eds, Interaction of Combinatorics and Representation Theory, pp. 95–145, Tokyo, 2001.
Mathematical Society of Japan. doi: 10.2969/msjmemoirs/01101C030.

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 and 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

