arXiv:1705.04596v1 [math.CO] 12 May 2017

A NOTE ON IDENTITIES IN PLACTIC MONOIDS AND
MONOIDS OF UPPER-TRIANGULAR TROPICAL MATRICES
ALAN J. CAIN, GEORG KLEIN, LUKASZ KUBAT, ANTÓNIO MALHEIRO,
AND JAN OKNIŃSKI
Abstract. This paper uses the combinatorics of Young tableaux to prove
the plactic monoid of inﬁnite rank does not satisfy a non-trivial identity, by
showing that the plactic monoid of rank n cannot satisfy a non-trivial identity
of length less than or equal to n. A new identity is then proven to hold for the
monoid of n × n upper-triangular tropical matrices. Finally, a straightforward
embedding is exhibited of the plactic monoid of rank 3 into the direct product
of two copies of the monoid of 3 × 3 upper-triangular tropical matrices, giving
a new proof that the plactic monoid of rank 3 satisﬁes a non-trivial identity.

1. Introduction
Whether the plactic monoid (the monoid of Young tableaux, which is famed for
its ubiquity [Lot02, Chapter 5]) and its finite-rank variants satisfy non-trivial identities is an actively-researched open question [KO15, Izh17]. Various monoids that are
related to the plactic monoid satisfy non-trivial identities. For instance, the Chinese
monoid [CEK+ 01], which has the same growth type as the plactic monoid [DK94],
satisfies Adian’s identity xyyxxyxyyx = xyyxyxxyyx [JO11, Corollary 3.3.4]. (This
is the shortest non-trivial identity satisfied by the bicyclic monoid [Adi66, Chapter IV, Theorem 2].) Furthermore, various ‘plactic-like’ monoids of combinatorial
objects satisfy non-trivial identities [CM]: for instance, the hypoplactic monoid
(the monoid of quasi-ribbon tableaux [KT97, Nov00]), the sylvester monoid (binary search trees [HNT05]), and the Baxter monoid (pairs of twin binary search
trees [Gir12]).
Let plac denote the (infinite-rank) plactic monoid and let placn denote the plactic
monoid of rank n, for any n ∈ N. First, plac1 is monogenic and thus commutative
and so trivially satisfies xy = yx. The monoid plac2 is isomorphic to the Chinese
monoid of rank 2 and so satisfies Adian’s identity. The third and fifth authors
proved that plac3 satisfies the identity uvvuvu = uvuvvu, where u(x, y) and v(x, y)
are respectively the left and right side of Adian’s identity (and so the identity
uvvuvu = uvuvvu has sixty variables x or y on each side) [KO15, Theorem 2.6].
Furthermore, plac3 does not satisfy Adian’s identity [KO15, p. 111–2]. Izhakian
developed a theory that allows one to show that plac3 is isomorphic to a subdirect
The
ﬁrst
author
was
supported
by
an
Investigador
FCT
fellowship
(IF/01622/2013/CP1161/CT0001).
For the ﬁrst and fourth 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/MHCFIL/2583/2014. Much of the research leading to this paper was undertaken during visits by
the ﬁrst and fourth authors to the University of Warsaw and these authors thank the university
for its hospitality.
1

2

A.J. CAIN, G. KLEIN, L. KUBAT, A. MALHEIRO, AND J. OKNIŃSKI

product of two copies of the monoid of 3×3 upper-triangular tropical matrices U3 (T)
[Izh17]. Since the same author had already proven that for any n ∈ N the monoid
of n × n upper-triangular tropical matrices Un (T) satisfies a non-trivial identity
[Izh14], this gives an alternative proof that plac3 satisfies a non-trivial identity. It
remains open whether placn satisfies a non-trivial identity for n ≥ 4.
This note contributes further to this topic. First, Section 3 uses the combinatorics of Young tableaux to prove that the infinite-rank plactic monoid plac does
not satisfy a non-trivial identity, in contrast to the Chinese, hypoplactic, sylvester,
and other monoids discussed above. Since plac is the union of all the finite-rank
plactic monoids placn , this implies that there is no non-trivial identity satisfied by
all the placn . However, it is still possible that there is a hierarchy of identities
satisfied by the various placn . Section 4 gives a new, simple, identity satisfied by
the monoid of n × n upper-triangular tropical matrices Un (T); the proof is based
on an approach developed by the fifth author [Okn15]. Finally, Section 5 gives an
elementary proof that plac3 embeds into the direct product of two copies of U3 (T);
this gives another proof that plac3 satisfies a non-trivial identity.

2. Preliminaries and notation
This section briefly recalls some definitions and sets up notation; see the references for further background.
An identity is a formal equality between two words in the free monoid, and is
non-trivial if the two words are distinct. A monoid M satisfies such an identity
if the equality holds in M under every substitution of letters in the words by
elements of M . For example, any commutative monoid satisfies the non-trivial
identity xy = yx.
For background on the plactic monoid, Young tableaux, and Schensted’s algorithm, see [Lot02, Ch.5]. Let A = {1 < 2 < · · ·} be the set of natural numbers
viewed as an infinite ordered alphabet. For n ∈ N, let An = {1 < 2 < · · · < n}
be the set of the first n natural numbers viewed as a finite ordered alphabet. For
any u ∈ A∗ , let Pplac (u) be the Young tableaux (the ‘plactic P-symbol’) computed
from u using Schensted’s algorithm. The plactic congruence ≡plac relates words in
A∗ that have the same image under u 7→ Pplac (u). The plactic monoid plac is the
factor monoid A∗/≡plac ; the plactic monoid of rank n is the factor monoid A∗n /≡plac
(where ≡plac is naturally restricted to A∗n ).
The tropical semiring is T = R ∪ {−∞}, and its addition and multiplication
operations ⊕ and ⊗ are defined by x ⊕ y = max{x, y} and x ⊗ y = x + y. The set
of n × n upper-triangular tropical matrices is denoted Un (T). (An upper-triangular
tropical matrix has all entries below the main diagonal equal to −∞, since this is
the additive identity of T.) For X, Y ∈ Un (T), write X ∼diag Y if X and Y have
equal corresponding diagonal entries.
Let ψ1 : Un (T) → Un−1 (T) be the map that sends a matrix Z ∈ Un (T) to the
matrix in Un−1 (T) obtained by erasing the rightmost column and bottommost row
of Z. Let ψ2 : Un (T) → Un−1 (T) be the map that sends a matrix Z ∈ Un (T) to the
matrix in Un−1 (T) obtained by erasing the leftmost column and topmost row of Z.
The maps ψ1 and ψ2 are monoid homomorphisms.

A NOTE ON IDENTITIES

3

3. The infinite-rank plactic monoid
Proposition 3.1. The plactic monoid placn does not satisfy any non-trivial identity
of length less than or equal to n.
Proof. Suppose, with the aim of obtaining a contradiction, that placn satisfies a nontrivial identity of length less than or equal to n. Without loss of generality, assume
that it satisfies such an identity over the variable set {x, y}, say u(x, y) = v(x, y) of
length equal to n (that is, with |u| = |v| = n). Interchanging u and v if necessary,
assume u is lexicographically less than v (where the variable set is ordered by
x < y). Suppose u(x, y) = u1 · · · un and v(x, y) = v1 · · · vn , where each ui and vi is
a variable x or y. If j is minimal such that uj and vj are different variables, then
uj is x and vj is y.
Let s = 12 · · · n ∈ A∗n and let t = 12 · · · (n − j)(n − j + 2) · · · n ∈ A∗n . (So
the word t does not contain the generator n − j + 1.) Since
placn satisfies the

identity u(x, y) = v(x, y), the equality u Pplac(s), Pplac (t) = v Pplac (s), Pplac (t)
holds. Thus the Young tableaux Pplac u(s, t) and Pplac v(s, t) are equal. In
particular, the height of the leftmost columns of these Young tableaux are equal.
By Schensted’s theorem [Sch61], the height of the leftmost column of Pplac (w) (for
w ∈ A∗ ) is equal to the length of the longest strictly decreasing subsequence in
w. Thus the lengths of the longest strictly decreasing subsequences of u(s, t) and
v(s, t) are equal.
Since s and t only contain symbols in {1, . . . , n}, the longest strictly decreasing
subsequences of u(s, t) and v(s, t) cannot be longer than n.
In u(s, t), there is a strictly decreasing subsequence of length n, namely n(n −
1) · · · 21, where, for i ∈ {1, . . . , n}, the symbol i is chosen from the instance of s or t
that was substituted for un−i+1 . Note in particular that since n−(n−j +1)+1 = j,
the symbol n − j + 1 is chosen from the instance of s substituted for uj (which is
the variable x). By the previous paragraph, n(n − 1) · · · 21 is a longest strictly
decreasing subsequence of u(s, t).
Thus v(s, t) must also have a strictly decreasing subsequence of length n. Since
each word s or t is strictly increasing, such a subsequence contains at most one
symbol chosen from the instance of s or t substituted for each vi . Since |v| = n,
this implies that exactly one symbol is chosen from each instance of s or t. Hence,
for i ∈ {1, . . . , n}, the symbol i must be chosen from the instance of s or t that was
substituted for vn−i+1 . In particular, since n − (n − j + 1) + 1 = j, the symbol
n − j + 1 is chosen from the instance of t substituted for vj (which is the variable
y). This is a contradiction, because the word t does not contain a symbol n − j + 1.
Therefore placn does not satisfy a non-trivial identity of length less than or equal
to n.


Since every finite-rank plactic monoid is a submonoid of the infinite-rank plactic
monoid, the following result is immediate from Proposition 3.1:
Theorem 3.2. The infinite-rank plactic monoid plac does not satisfy any nontrivial identity.

4

A.J. CAIN, G. KLEIN, L. KUBAT, A. MALHEIRO, AND J. OKNIŃSKI

4. A new identity for the monoid of upper-triangular tropical
matrices
Define
u0 (p, q) = p,

v0 (p, q) = q,

u1 (p, q) = pqppq,

v1 (p, q) = pqqpq,

and inductively define

un (p, q) = u1 un−1 (p, q), vn−1 (p, q) ,


vn (p, q) = v1 un−1 (p, q), vn−1 (p, q) .

for n ≥ 2. Note that the preceding equations hold for n = 1, but we only use them
as a definition for n ≥ 2. Note also that u1 (xy, yx) = v1 (xy, yx) is Adian’s identity.
Proposition 4.1. Let X, Y ∈ Un (T) with X ∼diag Y .
vn−1 (X, Y ).

Then un−1 (X, Y ) =

The proof strategy is similar to that used by the fifth author to show that Un (T)
satisfied a different set of identities [Okn15].
Proof. Proceed by induction on n. For n = 1, since the only entry of a 1 × 1
matrix is on its main diagonal, it follows from X ∼diag Y that X = Y ; hence
u0 (X, Y ) = X = Y = v0 (X, Y ). This is the base of the induction.
For the induction step, let n ≥ 2 and assume the result holds for n − 1. Let A =
un−2 (X, Y ) and B = vn−2 (X, Y ). Recall the homomorphisms ψ1 , ψ2 : Un (T) →
Un−1 (T) defined in Section 2. By the induction hypothesis,


un−2 ψ1 (X), ψ1 (Y ) = vn−2 ψ1 (X), ψ1 (Y ) and


un−2 ψ2 (X), ψ2 (Y ) = vn−2 ψ2 (X), ψ2 (Y ) .
Thus



ψ1 (A) = ψ1 un−2 (X, Y ) = ψ1 vn−2 (X, Y ) = ψ1 (B) and


ψ2 (A) = ψ2 un−2 (X, Y ) = ψ2 vn−2 (X, Y ) = ψ2 (B).

Therefore the matrices A and
 can differ only in their (1, n)-th entries.
 B
Denote the matrix C = cij by (c11 , c1n , cnn ; κ) for some suitable array κ representing the rest of C. That is,


c11
c1n


.
κ
(c11 , c1n , cnn ; κ) denotes 


cnn

Note that if D = (d11 , d1n , dnn ; µ), then


CD = c11 + d11 , max{c11 + d1n , c1n + dnn , γ}, cnn + dnn ; ν ,

for some γ and some array ν. In fact, γ is the maximum of the other sums of pairs
in the scalar product of the first row of C and first column of D and so is only
dependent on κ and µ (and not on c11 , c1n , cnn , d11 , d1n , or dnn ) and ν is only
dependent on κ, µ, c11 and dnn (and not on c1n , cnn , d11 , or d1n ).
So A = (c, a, d; κ1 ) and B = (c, b, d; κ1 ) for some c, a, b, d ∈ T and some array
κ1 . Then

AB = 2c, max{b + c, a + d, γ2 }, 2d, κ2

A NOTE ON IDENTITIES

5

for some γ2 ∈ T and array κ2 . Next,

ABA = (AB)A = 3c, max{a + 2c, b + c + d, a + 2d, d + γ2 , γ3 }, 3d; κ3 ,

ABB = (AB)B = 3c, max{b + 2c, b + c + d, a + 2d, d + γ2 , γ3 }, 3d; κ3 ;

for some γ3 ∈ T and array κ3 ; note that the these are equal in (AB)A and (AB)B
because they depend only on equal corresponding entries of A and B. Finally,
ABAAB = (ABA)AB = 5c, max{b + 4c, a + 3c + d, 3c + γ2 , a + 2c + 2d,

b + c + 3d, a + 4d, 4d + γ2 , 2d + γ3 , γ5 }, 5d; κ5 ,

ABBAB = (ABB)AB = 5c, max{b + 4c, a + 3c + d, 3c + γ2 , b + 2c + 2d,


b + c + 3d, a + 4d, 4d + γ2 , 2d + γ3 , γ5 }, 5d; κ5 ;

for some γ5 ∈ T and array κ5 ; note that these are equal in (ABA)AB and (ABB)AB
because they depend only on equal corresponding entries of ABA and ABB. Note
that the expressions for ABAAB and ABBAB only differ in the terms a + 2c + 2d
and b + 2c + 2d, respectively.
Now consider the four possible relative orders of a and b and of c and d. In each
case, there is some element that appears in the max{. . .} terms of the expressions
for both ABAAB and ABBAB and that is greater than both a + 2c + 2d and
b + 2c + 2d:
a ≥ b ∧ c ≥ d =⇒ a + 3c + d ≥ a + 2c + 2d, b + 2c + 2d;
a ≥ b ∧ c ≤ d =⇒ a + 4d ≥ a + 2c + 2d, b + 2c + 2d;
a ≤ b ∧ c ≥ d =⇒ b + 4c ≥ a + 2c + 2d, b + 2c + 2d;
a ≤ b ∧ c ≤ d =⇒ b + c + 3d ≥ a + 2c + 2d, b + 2c + 2d.
So in each case, a + 2c + 2d and b + 2c + 2d are not the maximum terms in the
expressions for ABAAB and ABBAB. Thus u1 (A, B) = ABAAB = ABBAB =
v1 (A, B). Therefore un−1 (X, Y ) = u1 (A, B) = v1 (A, B) = vn−1 (X, Y ).
Hence, by induction, the result holds for all n.

Theorem 4.2. The monoid of n × n upper-triangular tropical matrices Un (T)
satisfies the identity un−1 (xy, yx) = vn−1 (xy, yx).
Proof. Let X, Y ∈ Un (T). Then XY ∼diag Y X; the result is immediate from
Proposition 4.1.

5. A tropical representation of plac3
For any w ∈ A+ and any p, q ∈ A, define:

the maximal length of a nondecreasing subsequence
wpq = in w with entries in the interval [p, q]
−∞

if p ≤ q,
if p > q.

∗

For the identity ε of A , define εpq = 0 if p = q and εpq = −∞ otherwise.
Define a map φn : A∗ → Un (T) by φn (w) = wpq .
Lemma 5.1. The map φn is a homomorphism.

Proof. Proceed by induction on n. If n = 1 then the claim is clear. Assume
that n ≥ 2 and recall the homomorphisms ψ1 , ψ2 : Un (T) → Un−1 (T) defined in
Section 2. Let ϑ1 = ψ1 ◦ φn and ϑ2 = ψ2 ◦ φn . Clearly, ϑ1 is simply φn−1 and is

6

A.J. CAIN, G. KLEIN, L. KUBAT, A. MALHEIRO, AND J. OKNIŃSKI

thus a homomorphism by the induction hypothesis. Furthermore, if w 7→ w is the
∗
map from {2, . . . , n} to A∗n−1 , extending a 7→ a − 1, then ϑ2 (w) = φn−1 (w) and
so is a homomorphism by the induction hypothesis.
By the definition of matrix multiplication in Un (T), it now remains to prove that
for every u, v ∈ Pn the (1, n)-th entries of φn (uv) and φn (u)φn (v) are equal for all
u, v ∈ A∗n . In other words,
(5.1)

(uv)1n = max{u11 + v1n , u12 + v2n , . . . , u1n + vnn }.

However, it is clear that the longest nondecreasing subsequence in the product
uv is of the form αβ, where for some j the word α is the longest nondecreasing
subsequence in u with entries in the interval [1, j] and β is the longest nondecreasing
subsequence of v with entries in the interval [j, n]. Therefore (5.1) indeed holds and
the result follows.
Thus, by induction on n, the map φn is a homomorphism from A∗n to Un (T). 
Lemma 5.2. The map φn factors to give a homomorphism φn : placn → Un (T).
Proof. Notice that the plactic relations (baa, aba), (bab, bba), (bca, bac), (cab, acb)
(for a < b < c), with a, b, c ∈ A, preserve wpq for any w ∈ A∗ and any p, q ∈ A.
This is easy to see by a direct verification of the possible cases: the intersection
{a, b, c} ∩ [p, q] is either a single generator, or is equal to {a, b}, {b, c} or {a, b, c}.
It follows that if u, v ∈ A∗n are such that u ≡plac v, then φn (u) = φn (v).

Define fn : A∗n → A∗n as follows. For any i ∈ An , define
fn (i) = n(n − 1) · · · (i + 1)(i − 1) · · · 1,
and for w = a1 · · · ak ∈ A∗n , where ai ∈ A, define fn (w) = fn (ak ) · · · fn (a1 ).
It is straightforward to prove that the antihomomorphism fn factors to give an
antihomomorphism
  fn : placn → placn .
Let F = Fij be the n × n tropical matrix with Fi,n+1−i = 0 for i = 1, 2, . . . , n
and all other entries being −∞. Define an involution πn : Un (T) → Un (T) by
x 7→ (F xF )T (conjugation by F composed with transposition); note that πn is an
antihomomorphism (and in fact an antiautomorphism, since it is bijective). Define
σn = πn ◦ φn ◦ fn ; since fn and πn are antihomomorphisms, σn is a homomorphism.
Finally, define
the homomorphism Ψ3 : plac3 → U3 (T) × U3 (T) by Ψ3 (u) =

φ3 (u), σ3 (u) .
Proposition 5.3. The map Ψ3 is an embedding.

Proof. An arbitrary element of plac3 has a unique representation by a word of the
form 3ζ 2δ 3ǫ 1α 2β 3γ , where ζ ≤ δ ≤ α and δ + ǫ ≤ α + β. (This is the ‘row reading’
of a Young tableau.) Notice that, by the definition of φ3 ,


α
α+β
α+β+γ
(5.2)
φ3 (3ζ 2δ 3ǫ 1α 2β 3γ ) = −∞ β + δ max{β + ǫ} + δ + γ  .
−∞ −∞
ζ +ǫ+δ
An arbitrary element of plac3 also has a unique representative of the form
u = (321)k1 (21)k2 (31)k3 1k4 (32)k5 2k6 3k7 ,

A NOTE ON IDENTITIES

7

for some ki ∈ N ∪ {0} and either k4 = 0 or k5 = 0. (This is the column reading of
a Young tableau.) Straightforward computation shows that

(21)k7 (31)k6 (31)k5 (21)k5




(32)k3 (21)k3 (32)k2 (31)k2 (32)k1 (31)k1 (21)k1 if k4 = 0,
f3 (u) =

(21)k7 (31)k6 (32)k4 (32)k3



if k5 = 0;
(21)k3 (32)k2 (31)k2 (32)k1 (31)k1 (21)k1
thus

f3 (u) =

(

(321)2k1 +k2 +k3 +k5 (21)k7 (31)k6 1k5 2k3 3k2
(321)2k1 +k2 +k3 (21)k7 (31)k6 (32)k4 2k3 3k2

if k4 = 0,
if k5 = 0.

Regardless of whether k4 = 0 or k5 = 0, the row reading of u (or more precisely
Pplac (u)) has the form:
3k1 2k1 +k2 3k3 +k5 1k1 +k2 +k3 +k4 2k5 +k6 3k7 .
By (5.2), φ3 (u) determines the following numbers:
k7 , k5 + k6 , k1 + k2 + k3 + k4 ,
(5.3)
k1 + k2 , k1 + k3 + k5 , max{k3 + k5 , k5 + k6 }.

The row reading of f (u) (or more precisely Pplac f (u) ) has the form:

32k1 +k2 +k3 +k5 22k1 +k2 +k3 +k5 +k7 32k1 +k2 +k3 +k4 +k5 +k6 12k1 +k2 +k3 +2k5 +k6 +k7 2k3 +k4 3k2 .

Therefore, since πn is bijective, we know by (5.2) that σ3 (u) determines the following
numbers:
k2 , k3 + k4 , 2k1 + k2 + k3 + 2k5 + k6 + k7 ,
(5.4)

2k1 + k2 + k3 + k5 + k7 ,

4k1 + 2k2 + 2k3 + k4 + 2k5 + k6 ,

max{k3 + k4 , 2k1 + k2 + k3 + k4 + k5 + k6 }.
Consider another elemenent u′ ∈ plac3 , with
′

′

′

′

′

′

′

u′ = (321)k1 (21)k2 (31)k3 1k4 (32)k5 2k6 3k7 ,
and suppose that φ3 (u) = φ3 (u′ ) and σ3 (u) = σ3 (u′ ). By (5.3), k7 = k7′ . By (5.4),
k2 = k2′ . Consequently, (5.3) implies that k1 = k1′ . Thus,
k3 + k4 = k3′ + k4′ ,

k3 + k5 = k3′ + k5′ ,

k5 + k6 = k5′ + k6′ ,

respectively by (5.3), (5.4), and (5.3) together with k1 = k1′ .
If k4 = k4′ = 0, then k3 = k3′ , and so k5 = k5′ , and so k6 = k6′ ; thus u = u′ .
Similarly, if k5 = k5′ = 0, then k6 = k6′ and k3 = k3′ , and so k6 = k6′ ; thus u = u′ .
So suppose that k4 = 0 and k5′ = 0. Then
k3 = k3 + k4 = k3′ + k4′ = k3′ + k5′ + k4′ = k3 + k5 + k4′ ;
so k5 +k4′ = 0 and so k5 = 0. Hence k6 = k6′ , and k3 = k3′ and so k4 = k4′ . Therefore
u = u′ . Parallel reasoning shows that k4′ = 0 and k5 = 0 implies u = u′ .
Therefore φ3 (u) = φ3 (u′ ) and σ3 (u) = σ3 (u′ ) implies u = u′ .

Hence the map Ψ3 : plac3 → U3 (T) × U3 (T) with Ψ3 (u) = φ3 (u), σ3 (u) is an
embedding.

Since Ψ3 embeds plac3 into the direct product of two copies of U3 (T), the following result is immediate from Theorem 4.2:
Corollary 5.4. plac3 satisfies u2 (xy, yx) = v2 (xy, yx).

8

A.J. CAIN, G. KLEIN, L. KUBAT, A. MALHEIRO, AND J. OKNIŃSKI

References
[Adi66]

S. Adian. ‘Deﬁning relations and algorithmic problems for groups and
semigroups’. Trudy Mat. Inst. Steklov,
85 (1966),
pp. 3–123. url:
http://www.mathnet.ru/eng/tm2766.
[CEK+ 01] J. Cassaigne, M. Espie, D. Krob, J.-C. Novelli, & F. Hivert. ‘The Chinese Monoid’.
Int. J. Alg. Comput., 11, no. 3 (2001), pp. 301–334. doi: 10.1142/S0218196701000425.
[CM]
A. J. Cain & A. Malheiro. ‘Identities in plactic, hypoplactic, sylvester, Baxter, and
related monoids’. arXiv: 1611.04151.
[DK94]
G. Duchamp & D. Krob. ‘Plactic-growth-like monoids’. In M. Ito & H. Jürgensen, eds,
Words, Languages and Combinatorics, II, p. 124–142, River Edge, NJ, 1994. World
Scientiﬁc.
[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.
[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.
[Izh14]
Z. Izhakian. ‘Semigroup identities in the monoid of triangular tropical matrices’. Semigroup Forum, 88, no. 1 (2014), pp. 145–161. doi: 10.1007/s00233-013-9507-6.
[Izh17]
Z. Izhakian. ‘Tropical plactic algebra, the cloaktic monoid, and semigroup representations’. 2017. arXiv: 1701.05156v1.
[JO11]
J. Jaszuńska & J. Okniński. ‘Structure of Chinese algebras’. J. Algebra, 346, no. 1
(2011), pp. 31–81. doi: 10.1016/j.jalgebra.2011.08.020.
[KO15]
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.
[KT97]
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.
[Lot02]
M. Lothaire. Algebraic Combinatorics on Words. No. 90 in Encyclopedia of Mathematics and its Applications. Cambridge University Press, 2002.
[Nov00]
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.
[Okn15]
J. Okniński. ‘Identities of the semigroup of upper triangular tropical matrices’. Comm.
Algebra, 43, no. 10 (2015), pp. 4422–4426. doi: 10.1080/00927872.2014.946141.
[Sch61]
C. Schensted. ‘Longest increasing and decreasing subsequences’. Canad. J. Math., 13
(1961), pp. 179–191. doi: 10.4153/CJM-1961-015-3.
Centro de Matemática e Aplicações (CMA), Faculdade de Ciências e Tecnologia,
Universidade Nova de Lisboa, 2829–516 Caparica, Portugal
E-mail address: a.cain@fct.unl.pt
Institute of Mathematics, University of Warsaw, Banacha 2, 02–097 Warsaw, Poland
E-mail address: gklein@mimuw.edu.pl
Institute of Mathematics, University of Warsaw, Banacha 2, 02–097 Warsaw, Poland
E-mail address: lukasz.kubat@mimuw.edu.pl
Centro de Matemática e Aplicações (CMA), 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
Institute of Mathematics, University of Warsaw, Banacha 2, 02–097 Warsaw, Poland
E-mail address: okninski@mimuw.edu.pl

