# Effective representations of Hecke-Kiselman monoids of type $A_{n}$

###### Abstract.

We prove effectiveness of certain representations of Hecke-Kiselman monoids of
type $A_{n}$ constructed by Ganyushkin and Mazorchuk and also construct
further classes of effective representations for these monoids. As a
consequence the effective dimension of monoids of type $A_{n}$ is determined.
We also show that odd Fibonacci numbers $F_{2n+1}$ appear as the cardinality
of certain bipartite HK-monoids and count the number of multiplicity free
elements in any HK-monoid of type $A_{n}$.

##  1\. Introduction

Let $S$ be a monoid and $\mathcal{R}$ an integral commutative domain. A
(finite dimensional) linear representation of $S$ over $\mathcal{R}$ is a
homomorphism $\varphi$ from $S$ to the semigroup $\mathrm{Mat}_{n\times
n}(\mathcal{R})$ of $n\times n$ matrices over $\mathcal{R}$. The
representation $\varphi$ is called effective if different elements of $S$ are
represented by different matrices. Note that a faithful representation of the
semigroup algebra $\mathcal{R}S$ induces an effective representation of $S$,
but the converse is false in general. The least $n\in\mathbb{N}$ such that $S$
has an effective representation in $\mathrm{Mat}_{n\times n}(\mathcal{R})$ is
called the _effective dimension_ (of $S$ over $\mathcal{R}$) and is denoted by
$\mathrm{eff}.\dim_{\mathcal{R}}(S)$. For finite semigroups the problem of
determining $\mathrm{eff}\dim_{\mathcal{R}}(S)$ is effectively computable when
$\mathcal{R}$ is an algebraically closed or a real closed field, see [8], but
giving the answer as a closed formula is usually very hard.

C. Kiselman defined in [6] a monoid generated by three operators $c,l,m$ with
origins in convexity theory and showed that it has presentation

(1.1) $K=\langle c,l,m:c^{2}=c,l^{2}=l,m^{2}=m\\\
clc=lcl=lc,cmc=mcm=mc,lml=mlm=ml\rangle.$

In [6] it was shown that $K$ has $2^{3}$ idempotents and that $K$ has an
effective representation by (nonnegative) integer valued $3\times 3$-matrices.

O. Ganyushkin and V. Mazorchuk generalized $K$ to a series of monoids $K_{n}$,
called _Kiselman monoids_ (unpublished) given by the following presentation:

$K_{n}=\langle c_{1},c_{2},\cdots,c_{n}:c_{i}^{2}=c_{i}\forall
i,c_{i}c_{j}c_{i}=c_{j}c_{i}c_{j}=c_{i}c_{j}\forall i\leq j\rangle.$

It was showed by G. Kudryavtseva and V. Mazorchuk in [7] that $K_{n}$ is a
finite monoid with $2^{n}$ idempotents and that $K_{n}$ has an effective
representation by (nonnegative) integer valued $n\times n$-matrices. The proof
of the latter fact is technically rather involved.

Let $\Gamma=(V(\Gamma),E(\Gamma))$ be a graph representing a disjoint union of
simply laced Dynkin diagrams, $W_{\Gamma}$ the corresponding Weyl group and
$\mathcal{H}_{q}(W_{\Gamma})$, where $q\in\mathcal{R}$, the Hecke algebra of
$W_{\Gamma}$. By specializing $q=0$ we obtain an algebra which is isomorphic
to the monoid algebra of the so-called $0$-Hecke monoid $\mathcal{H}_{\Gamma}$
which has the following presentation:

(1.2) $\mathcal{H}_{\Gamma}=\langle v\in V(\Gamma):v^{2}=v\forall v,\\\
vwv=wvw\text{ for all }\\{v,w\\}\in E(\Gamma),vw=wv\text{ for all
}\\{v,w\\}\not\in E(\Gamma)\rangle.$

O. Ganyushkin and V. Mazorchuk proposed in [3] a common generalization for
$K_{n}$ and $\mathcal{H}_{\Gamma}$ by introducing the so-called Hecke-Kiselman
monoids which are defined as follows.

######  Definition 1.1.

Let $\Gamma=\big{(}V(\Gamma),E(\Gamma)\big{)}$ be a simple directed graph. The
_Hecke-Kiselman monoid_ $HK_{\Gamma}$ of $\Gamma$ is the quotient of the free
monoid $\big{(}V(\Gamma)\big{)}^{*}$ by the following relations:

  1. (I)

$x^{2}=x$ for all $x\in V(\Gamma)$.

  2. (II)

If there is no edge between $x$ and $y$, then $xy=yx$.

  3. (III)

If there is an edge from $x$ to $y$ but no edge from $y$ to $x$, then
$xyx=yxy=xy$.

  4. (IV)

If there are edges in both directions between $x$ and $y$, then $xyx=yxy$.

We will refer to the above relations (including $x^{2}=x$) as _edge
relations_. Since there is no risk of confusion we will use $x\in\Gamma$ as a
shorthand for $x\in V(\Gamma)$.

It is often convenient to think of a pair of edges $x\to y$ and $y\to x$ in
$\Gamma$ as a single undirected edge. In order to simplify statements this
identification is done for the rest of the paper. Both Kiselman and $0$-Hecke
monoids are special cases of Hecke-Kiselman monoids. The $0$-Hecke monoid
corresponds to the underlying undirected graph of a Dynkin diagram. The
Kiselman monoid $K_{n}$ corresponds to $\Gamma$ for which
$V(\Gamma)=\\{1,2\cdots,n\\}$ and edge set $E(\Gamma)=\\{(i,j)|i<j\\}$. O.
Ganyushkin and V. Mazorchuk proved that the semigroups $HK_{\Gamma}$ and
$HK_{\Gamma^{\prime}}$ are isomorphic if and only if $\Gamma$ and
$\Gamma^{\prime}$ are isomorphic graphs.

######  Definition 1.2.

A simple directed graph $\Gamma$ is of _type $A_{n}$_ if its underlying
undirected graph is the Dynkin diagram $A_{n}$ for some $n\in\mathbb{N}$. A
graph of type $A_{n}$ with exactly one sink and one source (which may
coincide) and no unoriented edges is called _linearly ordered_. A _canonical
order_ on the vertices of a graph of type $A_{n}$ is one where neighboring
vertices have indices that differ by 1. The canonical order on a linearly
ordered graph is from a source to a sink, i.e.

$\lx@xy@svg{\hbox{\raise 0.0pt\hbox{\kern
7.003pt\hbox{\ignorespaces\ignorespaces\ignorespaces\hbox{\vtop{\kern
0.0pt\offinterlineskip\halign{\entry@#!@&&\entry<EMAIL_ADDRESS>0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{v_{1}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{\hbox{\kern
31.003pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern
31.003pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise
0.0pt\hbox{$\textstyle{v_{2}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{\hbox{\kern
69.00902pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern
69.00902pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise
0.0pt\hbox{$\textstyle{\cdots\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{\hbox{\kern
106.50902pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern
106.50902pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise
0.0pt\hbox{$\textstyle{v_{n}}$}}}}}}}\ignorespaces}}}}\ignorespaces.$

We will say that $HK_{\Gamma}$ is of type $A_{n}$ if $\Gamma$ is of type
$A_{n}$. The monoids $HK_{\Gamma}$ of type $A_{n}$ naturally appear as monoid
of projection functors as defined by A.-L. Grensing in [4, 9], see also some
further development in [5].

In view of the above the following questions arise naturally:

  1. (1)

Does $HK_{\Gamma}$ have $2^{n}$ idempotents, where $n=|V(\Gamma)|$ is the
number of vertices? If not, then how many?

  2. (2)

Does $HK_{\Gamma}$ have an effective representation by $n\times n$\- matrices
over some $\mathcal{R}$? over $\mathbb{Z}$?

  3. (3)

Is $HK_{\Gamma}$ finite? Can we calculate its cardinality?

These are the questions which we address in the present paper for various
families of graphs. After the first version of the present paper appeared, R.
Aragona and A. D’Andrea addressed the cardinality problem in the case $\Gamma$
is small (has at most four vertices) and discovered a nontrivial example of a
graph with an unoriented edge for which the cardinality of the Hecke-Kiselman
monoid is infinite, see [2]. In this paper we study only graphs for which
there are no unoriented edges, or, equivalently, there is at most one oriented
edge between any pair of vertices.

The paper is organized as follows: In Section 2 we collected some basic
notation and definitions from the combinatorics of words. Section 3 some
preliminary results on linear representations of some Hecke-Kiselman monoids.
In Section 4 we discuss effective representations and cardinalities of the
Hecke-Kiselman monoids considered in Section 3. In Section 5 we investigate
obstructions to generalize our methods to further classes of Hecke-Kiselman
monoids.

All representations in this paper are linear. We set
$\underline{n}=\\{1,2,\cdots,n\\}$.

##  2\. Words, content and canonical projections

If $\Gamma$ is a disjoint union of $\Gamma_{1}$ and $\Gamma_{2}$, then it is
easy to see that

$HK_{\Gamma}=HK_{\Gamma_{1}}\oplus HK_{\Gamma_{2}}.$

Thus we only need to study connected graphs.

We will use bold fonts to denote a word
$\mathbf{w}\in\big{(}V(\Gamma)\big{)}^{*}$. Elements in $HK_{\Gamma}$ are
equivalence classes of words and are denoted by brackets: $[\mathbf{w}]\in
HK_{\Gamma}$. The empty word is denoted by $\varepsilon$. We will make use of
two binary relations on $\big{(}V(\Gamma)\big{)}^{*}$:

$\mathbf{w}\sim\mathbf{w}^{\prime}:\iff[\mathbf{w}]=[\mathbf{w}^{\prime}],\text{
and}$
$\mathbf{w}\approx\mathbf{w}^{\prime}:\iff\big{(}\mathbf{w}=\mathbf{xyz}\text{
and }\mathbf{w}^{\prime}=\mathbf{xy^{\prime}z},\text{ where
}\mathbf{y}=\mathbf{y^{\prime}}\text{ is an edge relation.}\big{)}$

Note that $\sim$ is an equivalence relation while $\approx$ is not. Moreover,
$\sim$ is the transitive closure of $\approx$. Hence the statement
$\mathbf{w}\approx\mathbf{w}^{\prime}$ is stronger than the statement
$\mathbf{w}\sim\mathbf{w}^{\prime}$.

For each word $\mathbf{w}$ we may define the content
$\mathfrak{c}(\mathbf{w})\subset V(\Gamma)$ as the set of vertices that appear
at least once in $\mathbf{w}$. Note that the equality
$\mathfrak{c}(\mathbf{w})=\mathfrak{c}(\mathbf{w}^{\prime})$ holds for each of
the edge relations $\mathbf{w}=\mathbf{w}^{\prime}$. Since
$\mathfrak{c}(\mathbf{xyz})=\mathfrak{c}(\mathbf{x})\cup\mathfrak{c}(\mathbf{y})\cup\mathfrak{c}(\mathbf{z})$,
this implies $\mathfrak{c}(\mathbf{w})=\mathfrak{c}(\mathbf{w}^{\prime})$ when
$\mathbf{w}\approx\mathbf{w}^{\prime}$, and, by transitivity, when
$\mathbf{w}\sim\mathbf{w}^{\prime}$. Thus we may define the content
$\mathfrak{c}([\mathbf{w}])$ for each element in $[\mathbf{w}]\in
HK_{\Gamma}$. Note that
$\mathfrak{c}([\mathbf{w}][\mathbf{w}^{\prime}])=\mathfrak{c}([\mathbf{w}])\cup\mathfrak{c}([\mathbf{w}^{\prime}])$.
In particular $\mathfrak{c}([\mathbf{w}])=\mathfrak{c}([\mathbf{w}^{\prime}])$
implies $\mathfrak{c}([\mathbf{w}])=\mathfrak{c}([\mathbf{ww^{\prime}}])$ and
the set of elements with a fixed content form a subsemigroup. In this way we
obtain a semilattice decomposition of $HK_{\Gamma}$.

Let $\Gamma^{\prime}\subset\Gamma$ be a subgraph. Then $HK_{\Gamma^{\prime}}$
is a submonoid of $HK_{\Gamma}$ in the natural way. Furthermore, sending each
$x\in V(\Gamma^{\prime})$ to itself and each $x\in
V(\Gamma\setminus\Gamma^{\prime})$ to $\varepsilon$ extends uniquely to a
homomorphism $p:HK_{\Gamma}\to HK_{\Gamma^{\prime}}$ which is obviously
surjective and hence will be called the canonical projection. Therefore
$HK_{\Gamma^{\prime}}$ is a retract of $HK_{\Gamma}$.

##  3\. Preliminary results

Let $\mathcal{R}$ be an integral domain and $W=\bigoplus_{v\in
V(\Gamma)}\mathcal{R}v$ the formal vector space over $\mathcal{R}$ with basis
$V(\Gamma)$. Let $f:E(\Gamma)\to\mathcal{R}\setminus\\{0\\}$ be a function (we
will call it a weight function). For notational reasons we denote the weight
on the edge from $x$ to $y$ by $f_{xy}$ (assuming it exists). Set

$\theta_{x}^{f}(y)=\begin{cases}y,&x\neq y;\\\ \sum_{z\to
x}f_{zx}z,&x=y;\end{cases}$

and extend this by linearity to an endomorphism of $W$. Define the map
$R_{f}:V(\Gamma)\to End_{\mathcal{R}}(W)$ by $x\mapsto\theta_{x}^{f}$. This
uniquely extends to a homomorphism $R_{f}:\big{(}V(\Gamma)\big{)}^{*}\to
End_{\mathcal{R}}(W)$ using the fact that $V(\Gamma)$ is a set of free
generators of $\big{(}V(\Gamma)\big{)}^{*}$. The endomorphisms
$\theta_{x}^{f}$ will be called _atomic_. If the weight function is fixed in
advance, we sometimes omit it from the notation and write simply $\theta_{x}$
for $\theta_{x}^{f}$. This construction generalizes the construction of
“linear integral representations” in [3], and the following statement
generalizes [3, Proposition 7].

######  Theorem 3.1.

$R_{f}$ induces a well-defined homomorphism $HK_{\Gamma}\to
End_{\mathcal{R}}(W)$.

###### Proof.

We have to check that $R_{f}$ respects the edge relations. We start with the
relation $x^{2}=x$. Since $\Gamma$ is simple, an edge $z\to x$ implies $z\neq
x$. Thus

$\theta_{x}\circ\theta_{x}(y)=\begin{cases}y,&x\neq y;\\\ \sum_{z\to
x}f_{zx}\theta_{x}(z),&x=y\end{cases}=\begin{cases}y,&x\neq y;\\\ \sum_{z\to
x}f_{zx}z,&x=y\end{cases}=\theta_{x}(y).$

Relation $xy=yx$ for $x$ and $y$ different and non-adjacent.

$\theta_{x}\circ\theta_{y}(z)=\begin{cases}\theta_{x}(z),&y\neq z;\\\
\sum_{\omega\to y}f_{\omega
y}\theta_{x}(\omega),&y=z\end{cases}=\begin{cases}z,&x,y\neq z;\\\
\sum_{\omega\to x}f_{\omega x}\omega,&x=z;\\\ \sum_{\omega\to y}f_{\omega
y}\omega,&y=z.\end{cases}$

As the right hand side is symmetric in $x$ and $y$, so is the left hand side.

Relation $xyx=yxy=xy$ when there is a directed edge from $x$ to $y$.

$\theta_{x}\circ\theta_{y}\circ\theta_{x}(z)=\begin{cases}\theta_{x}\circ\theta_{y}(z),&x\neq
z;\\\ \sum_{\omega\to x}f_{\omega
x}\theta_{x}\circ\theta_{y}(\omega),&x=z\end{cases}=\begin{cases}z,&x,y\neq
z;\\\ \sum_{\omega\to y}f_{\omega y}\theta_{x}(\omega),&y=z;\\\
\sum_{\omega\to x}f_{\omega x}\omega,&x=z.\end{cases}$

Since there is a directed edge from $x$ to $y$ we have

$\sum_{\omega\to y}f_{\omega y}\theta_{x}(\omega)=\sum_{\omega\to
y,x\neq\omega}f_{\omega y}\omega+f_{xy}\sum_{\omega\to x}f_{\omega x}\omega.$

On the other hand

$\theta_{x}\circ\theta_{y}(z)=\begin{cases}\theta_{x}(z),&y\neq z;\\\
\sum_{\omega\to y}f_{\omega
y}\theta_{x}(\omega),&y=z\end{cases}=\begin{cases}z,&x,y\neq z;\\\
\sum_{\omega\to x}f_{\omega x}\omega,&x=z;\\\ \sum_{\omega\to y}f_{\omega
y}\theta_{x}(\omega),&y=z;\end{cases}$

This implies $xyx=xy$. Observe that $\theta_{x}\circ\theta_{y}(z)$ has no $y$
component for any $z$. Thus, by definition $\theta_{y}$ acts as identity on
$\theta_{x}\circ\theta_{y}(z)$ and we get $xy=yxy$. ∎

In the case $\Gamma$ is linearly ordered of type $A_{n}$, $f$ is constantly
equal to $1$ and $\mathbb{Z}\subset\mathcal{R}$ we have that $R_{f}$ is
effective, as proved in [3]. We denote a constant function
$E(\Gamma)\to\mathcal{R}$ with value $c$ simply by $c\in\mathcal{R}$ and the
corresponding representation by $R_{c}$.

######  Lemma 3.2.

Let $\Gamma$ be linearly ordered of type $A_{n}$. Then any choice of $f$ gives
an effective representation $R_{f}$ of $HK_{\Gamma}$.

It is important to recall that all values of $f$ are non-zero by definition.

###### Proof.

For a linearly ordered $\Gamma$ of type $A_{n}$ each vertex of $\Gamma$ is a
target of at most one arrow. Therefore the definition of $R_{f}$ implies that
for any $v,x\in V(\Gamma)$ the linear transformation $R_{f}([v])$ maps $x$ to
a scalar multiple of some other vertex, say $y$. By induction on the length of
a word it follows that for any $x\in V(\Gamma)$ and $[\mathbf{w}]\in
HK_{\Gamma}$ there exists $v\in V(\Gamma)$ and
$c_{x,f,\mathbf{w}}\in\mathcal{R}$ such that
$R_{f}([\mathbf{w}])(x)=c_{x,f,\mathbf{w}}y$. Certainly, $c_{x,f,\mathbf{w}}$
depends on $f$. However, we claim that

(3.1) $c_{x,f,\mathbf{w}}\neq 0\quad\text{ implies that }\quad
c_{x,f^{\prime},\mathbf{w}}\neq 0\quad\text{ for any other }\quad f^{\prime},$

or, in other words, that the fact that $c_{x,f,\mathbf{w}}$ is non-zero does
not depend on $f$. Claim (3.1) and effectiveness of $R_{1}$ established in [3]
imply the claim of our lemma.

To prove claim (3.1) assume that $c_{x,f,\mathbf{w}}\neq 0$. Let
$w=w_{k}w_{k-1}\cdots w_{1}$ and set $y_{0}=x$. For $i=1,\dots,k$ define
recursively $y_{i}$ as the unique vertex of $\Gamma$ such that
$R_{f}([w_{i}w_{i-1}\cdots w_{1}])(x)=c_{i}y$ for some non-zero
$c_{i}\in\mathcal{R}$. This is well-defined as $c_{x,f,\mathbf{w}}\neq 0$. We
have $c_{k}=c_{x,f,\mathbf{w}}\neq 0$. The definition of $R_{f}$ and the fact
that $\mathcal{R}$ is a domain imply that for $f^{\prime}$ we will have that
$R_{f^{\prime}}([w_{i}w_{i-1}\cdots w-1])(x)=c^{\prime}_{i}y$ for some non-
zero $c^{\prime}_{i}\in\mathcal{R}$. In particular, $c^{\prime}_{k}\neq 0$ and
the claim follows. ∎

######  Remark 3.3.

We note that the representation $R_{f}$ is not effective if $\Gamma$ contains
even a single unoriented edge. Let $\Gamma$ be a graph containing the vertices
$v$ and $w$ with an unoriented edge in between. To simplify notation, let

$A=\sum_{z\to v,z\neq w}f_{zv}z\text{ and }B=\sum_{z\to w,z\neq v}f_{zw}z.$

From the definition of $R_{f}$ we have

$\theta_{v}\circ\theta_{w}\circ\theta_{v}(v)=f_{wv}\theta_{v}\circ\theta_{w}(w+A)=f_{wv}A+f_{wv}f_{vw}\theta_{v}(v+B)=$
$f_{wv}A+f_{wv}f_{vw}B+f_{wv}^{2}f_{vw}A+f_{wv}^{2}f_{vw}w,\text{ while}$
$\theta_{w}\circ\theta_{v}\circ\theta_{w}(v)=\theta_{w}\circ\theta_{v}(v)=f_{wv}\theta_{w}(w+A)=f_{wv}A+f_{wv}f_{vw}B+f_{wv}f_{vw}v.$

As $v$ and $w$ are linearly independent, we must have $f_{wv}f_{vw}=0$. Since
$\mathcal{R}$ is an integral domain, this implies $f_{wv}=0$ or $f_{vw}=0$.
But $f$ only takes nonzero values by definition. If we allow $f$ to be zero on
an edge $v\to w$ then straightforward calculations show that
$R_{f}[wv]=R_{f}[vwv]$, showing that $f$ is not effective.

We will say that a word $\mathbf{w}$ is _multiplicity free with respect to a
vertex $v$_ if $v$ appears at most once in $\mathbf{w}$. A word $\mathbf{w}$
is called _multiplicity free_ if it is multiplicity free with respect to every
vertex. An element $[\mathbf{w}]\in HK_{\Gamma}$ is called _multiplicity free_
if $[\mathbf{w}]$ contains a multiplicity free word. For $A\subset V(\Gamma)$
define $\mathcal{MF}_{A}\subset\big{(}V(\Gamma)\big{)}^{*}$ as the set of
words which are multiplicity free with respect to all vertices in $A$. Let
$\mathcal{S}=\mathcal{S}_{\Gamma}\subset V(\Gamma)$ denote the set of all
sources and sinks. Multiplicity free words are easier to handle because they
allow us to speak about _the_ position of a single vertex (assuming it does).
Recall that a subword of a word $v_{1}v_{2}\dots v_{k}$ is a word of the form
$v_{i_{1}}v_{i_{2}}\dots v_{i_{j}}$ where $1\leq i_{1}<i_{2}<\dots<i_{j}\leq
k$.

######  Lemma 3.4.

Let $A\subset\mathcal{S}$ and $\mathbf{w}\in\big{(}V(\Gamma)\big{)}^{*}$. Then
$[\mathbf{w}]\cap\mathcal{MF}_{A}$ contains a subword of $\mathbf{w}$.
Furthermore, if $\mathbf{w}\sim\mathbf{w}^{\prime}$ are both in
$\mathcal{MF}_{A}$, then there exist a series of words
$\mathbf{w}_{i}\in[\mathbf{w}]\cap\mathcal{MF}_{A}$, such that

$\mathbf{w}=\mathbf{w}_{1}\approx\mathbf{w}_{2}\approx\cdots\approx\mathbf{w}_{k}=\mathbf{w}^{\prime}.$

###### Proof.

If $\mathbf{w}$ is already in $\mathcal{MF}_{A}$, we take
$\mathbf{w}^{\prime}=\mathbf{w}$ and we are done. Assume that
$\mathbf{w}=\mathbf{w}_{1}a\mathbf{w}_{2}a\mathbf{w}_{3}$ is a word with at
least two occurrences of $a\in A$, and that $a$ is a source (if $a$ is a sink,
a similar argument works with all words reversed). Because of our restrictions
on $\Gamma$, for any $x\in V(\Gamma)$ we have one of the following:

  1. (1)

$x=a$ and $ax=aa=aaa=axa$;

  2. (2)

there is a directed edge from $a$ to $x$ and $ax=axa$;

  3. (3)

$a$ and $x$ are nonadjacent and $ax=aax=axa$.

Note that in all cases we have the relation $ax=axa$. Therefore, for
$\mathbf{w}_{2}=x_{1}x_{2}\cdots x_{k}$ we have

$\mathbf{w}=\mathbf{w}_{1}ax_{1}x_{2}\cdots
x_{k}a\mathbf{w}_{3}\sim\mathbf{w}_{1}ax_{1}ax_{2}\cdots
x_{k}a\mathbf{w}_{3}\sim\cdots\sim\mathbf{w}_{1}ax_{1}ax_{2}a\cdots
ax_{k}a\mathbf{w}_{3}\sim$ $\mathbf{w}_{1}ax_{1}ax_{2}a\cdots
ax_{k}\mathbf{w}_{3}\sim\cdots\sim\mathbf{w}_{1}ax_{1}x_{2}\cdots
x_{k}\mathbf{w}_{3}=\mathbf{w}_{1}a\mathbf{w}_{2}\mathbf{w}_{3}.$

Thus we have lowered the multiplicity of $a$ in $\mathbf{w}$ while leaving all
other vertices untouched. Continuing in this fashion for all $a\in A$ gives us
the desired subword of $\mathbf{w}$ contained in
$[\mathbf{w}]\cap\mathcal{MF}_{A}$. This proves the first claim of the lemma.

Given two words $\mathbf{w}\sim\mathbf{\tilde{w}}$ there is, by definition, a
sequence of words $\mathbf{w}_{i}\in[\mathbf{w}]$, $i\in\underline{k}$, such
that

$\mathbf{w}=\mathbf{w}_{1}\approx\mathbf{w}_{2}\approx\cdots\approx\mathbf{w}_{k}=\mathbf{\tilde{w}}.$

Let $\psi:\big{(}V(\Gamma)\big{)}^{*}\to\mathcal{MF}_{A}$ be the function
which removes all superfluous occurrences of all $a\in A$ as described above.
We want to show that if $\mathbf{a}\approx\mathbf{b}$, then
$\psi(\mathbf{a})\approx\psi(\mathbf{b})$ or
$\psi(\mathbf{a})=\psi(\mathbf{b})$ (in which case we may shorten the
sequence). By definition, $\mathbf{a}\approx\mathbf{b}$ means that
$\mathbf{a}=\mathbf{a}_{l}\mathbf{c}\mathbf{a}_{r}$ and
$\mathbf{b}=\mathbf{a}_{l}\mathbf{d}\mathbf{a}_{r}$, where
$\mathbf{c}=\mathbf{d}$ is an edge relation. Depending on the letters which
appear in the edge relation, we consider different cases.

Case 1. Relation $x^{2}=x,xyx=yxy=xy$ or $xy=yx$ for $x,y\not\in A$. In this
case the application of $\psi$ affects neither $\mathbf{c}$ nor $\mathbf{d}$.
Assume that $a\in A$ is a source which appears in exactly one of the words
$\mathbf{a}_{l}$ or $\mathbf{a}_{r}$. Then the application of $\psi$ to both
$\mathbf{a}$ and $\mathbf{b}$ deletes all but the leftmost occurrences of $a$.
If $a\in A$ is a source which appears in both $\mathbf{a}_{l}$ and
$\mathbf{a}_{r}$, then the application of $\psi$ to both $\mathbf{a}$ and
$\mathbf{b}$ deletes all occurrences of $a$ in $\mathbf{a}_{r}$ and all but
the leftmost occurrences of $a$ in $\mathbf{a}_{l}$. Similarly one considers
the case when $a\in A$ is a sink. It follows that
$\psi(\mathbf{a})\approx\psi(\mathbf{b})$ in this case.

Case 2. Relations $a^{2}=a,ax=xa$ and $axa=xax=ax$ where $a\in A$ and
$x\not\in A$. We assume that $a$ is a source (the case when $a$ is a sink is
done similarly). If $a$ appears in $\mathbf{a}_{l}$, then $\psi$ deletes all
$a$ in $\mathbf{a}_{r}$, $\mathbf{c}$ and $\mathbf{d}$ (and leaves just the
leftmost occurrences of $a$ in $\mathbf{a}_{l}$). Note that our edge relations
become $\varepsilon=\varepsilon$, $x=x$ and $x=x^{2}$, respectively. It
follows that in this case $\psi(\mathbf{a})=\psi(\mathbf{b})$ or
$\psi(\mathbf{a})\approx\psi(\mathbf{b})$. If $a$ does not appear in
$\mathbf{a}_{l}$, then $\psi$ deletes all $a$ in $\mathbf{a}_{r}$ and leaves
the leftmost occurrences of $a$ in $\mathbf{c}$ and $\mathbf{d}$. Note that
our edge relations become $a=a$, $ax=xa$ and $ax=xax$, respectively. It
follows that in this case we have either
$\psi(\mathbf{a})\approx\psi(\mathbf{b})$ or
$\psi(\mathbf{a})=\psi(\mathbf{b})$, depending on the edge relation.

Case 3. Relation $ab=ba$ where $a,b\in A$. Similarly to the above, the
application of $\psi$ does the same thing to the subword $\mathbf{a}_{l}$ of
both $\mathbf{a}$ and $\mathbf{b}$, it does the same thing to the subword
$\mathbf{a}_{r}$ of both $\mathbf{a}$ and $\mathbf{b}$, and it maps $ab=ba$ to
either $ab=ba$ or $a=a$ or $b=b$ or $\varepsilon=\varepsilon$, depending on
whether $a$ or $b$ appear in $\mathbf{a}_{l}$ (if they are sources) or in
$\mathbf{a}_{r}$ (if they are sinks). In all cases we get that either
$\psi(\mathbf{a})\approx\psi(\mathbf{b})$ or
$\psi(\mathbf{a})=\psi(\mathbf{b})$.

Case 4. Relation $aba=bab=ab$, where $a,b\in A$. Here $a$ is a source and $b$
is a sink. Similarly to the above, the application of $\psi$ does the same
thing to the subword $\mathbf{a}_{l}$ of both $\mathbf{a}$ and $\mathbf{b}$
and it does the same thing to the subword $\mathbf{a}_{r}$ of both
$\mathbf{a}$ and $\mathbf{b}$. Depending on the appearance of $a$ in
$\mathbf{a}_{l}$ and $b$ in $\mathbf{a}_{r}$, the relation is either mapped to
$ab=ab$ or to $a=a$ or to $b=b$ or to $\varepsilon=\varepsilon$. Again, in all
cases we get that either $\psi(\mathbf{a})\approx\psi(\mathbf{b})$ or
$\psi(\mathbf{a})=\psi(\mathbf{b})$. The claim follows. ∎

######  Lemma 3.5.

Let $\Gamma$ be a simple directed graph with at most one edge between any pair
of vertices. Let $\Gamma^{\prime}\subset\Gamma$ be a full subgraph and let
$\mathbf{w}$ be a word such that
$\mathfrak{c}[\mathbf{w}]=V(\Gamma^{\prime})$. Then exactly one of the
following alternatives takes place:

  1. (1)

$\Gamma^{\prime}$ contains an oriented cycle and $[\mathbf{w}]^{k}$ are
pairwise distinct for all $k\in\mathbb{N}$.

  2. (2)

$\Gamma^{\prime}$ contains no oriented cycles and
$[\mathbf{w}]^{|V(\Gamma^{\prime})|}$ equals the zero element in
$HK_{\Gamma^{\prime}}$.

###### Proof.

Assume first that $\Gamma^{\prime}$ contains an oriented cycle $C$ (which then
necessarily has length at least $3$). Using $p:HK_{\Gamma}\to HK_{C}$ it is
enough to prove the first claim under the assumption
$\Gamma=\Gamma^{\prime}=C$ (since if $p([\mathbf{w}]^{k})$ are pairwise
distinct then $[\mathbf{w}]^{k}$ are pairwise distinct as well).

Let the vertices in $C$ be enumerated by $\mathbb{Z}_{n}$, such that there is
a directed edge from $v_{i}$ to $v_{i+1}$ for all $i\in\underline{n}$. To
separate elements, we choose the representation $R_{2}$ (with the ground ring
$\mathcal{R}=\mathbb{Z}$) and prove that the images $R_{2}([\mathbf{w}^{k}])$
are pairwise different. Recall that each $\theta_{i}$ maps $v_{i}$ to
$2v_{i-1}$ and $v_{j}$ to $v_{j}$ for $j\neq i$. It follows that there is a
transformation $t:V(C)\to V(C)$ and a set of nonnegative integers
$m_{1},\cdots,m_{n}$ such that $R_{2}([\mathbf{w}])(v_{i})=2^{m_{i}}v_{t(i)}$.
Moreover, $\mathfrak{c}([\mathbf{w}])=V(C)$ implies that $m_{i}\geq 1$ for
each $i$. We define the sequence $n_{i}$ by
$R_{2}([\mathbf{w}])(v_{t^{i-1}(1)})=2^{n_{i}}v_{t^{i}(1)}$, and
$\overline{n_{i}}=\sum_{j=1}^{i}n_{i}$. Then

$R_{2}([w^{k}])(v_{1})=2^{n_{1}}R_{2}([w^{k-1}])(v_{t(1)})=\cdots=2^{\overline{n_{k}}}v_{t^{k}(1)}.$

Since the exponent is strictly increasing in $k$, it follows that $[w^{k}]$
are pairwise distinct.

Assume now that $\Gamma$ contains no oriented cycles. In this case
$HK_{\Gamma}$ is a quotient of Kiselman’s semigroup and hence the second claim
follows from [7, Lemma 12]. ∎

######  Theorem 3.6.

There is a bijection between idempotents in $HK_{\Gamma}$ and full subgraphs
of $\Gamma$ which do not contain any oriented cycles.

###### Proof.

Let $[\mathbf{w}]\in\Gamma$ be an idempotent and $\Gamma^{\prime}$ be the full
subgraph whose set of vertices is $\mathfrak{c}[\mathbf{w}]$. Then
$\Gamma^{\prime}$ contains no oriented cycles by the first claim of the
previous lemma.

Conversely, let $\Gamma^{\prime}$ be a full subgraphs of $\Gamma$ which does
not contain any oriented cycles. Then $HK_{\Gamma^{\prime}}$ is a quotient of
Kiselman’s semigroup, in particular, $HK_{\Gamma^{\prime}}$ is finite and
contains a unique idempotent of maximal content, namely the zero element, see
[7]. The claim follows. ∎

##  4\. Main results

In every graph of type $A_{n}$ there are sinks and sources where the direction
of the edges changes. Thus we have small linearly ordered pieces of the graph,
glued together in sources an sinks. Since we know a lot about effective
representations for the pieces (see the previous paragraph), we would like to
know what the gluing does to representations.

######  Definition 4.1.

Given a graph $\Gamma$ and a vertex $a\in\Gamma$ the _source graph_ $S_{a}$ is
the full subgraph of $\Gamma$ with the vertex set

$V(S_{a})=\\{v\in\Gamma|\text{ there exists a directed path from }v\text{ to
}a\\}.$

######  Lemma 4.2.

For a vertex $a\in\Gamma$ let $p_{a}:HK_{\Gamma}\to HK_{S_{a}}$ be the
projection morphism. Then for any $[\mathbf{w}]\in HK_{\Gamma}$ we have the
equality $R_{f}([\mathbf{w}])(a)=R_{f}(p_{a}([\mathbf{w}]))(a)$.

###### Proof.

Let $x\in V(\Gamma)$ and $v\in S_{a}$. From the definition of $R_{f}$ we have
the equality $R_{f}([x])(v)=\sum_{w\in S_{a}}c_{w}w$ for some constants
$c_{v}$. Therefore the linear span $L$ of all $v\in S_{a}$ is invariant with
respect to the action of $HK_{\Gamma}$. Furthermore, for any $x\in
V(\Gamma)\setminus S_{a}$ we have $R_{f}([x])(v)=v$ for all $v\in S_{a}$,
which means that $R_{f}([x])$ acts as the identity on $L$. It follows that the
actions of $R_{f}([\mathbf{w}])$ and $R_{f}(p_{a}([\mathbf{w}]))$ on $L$
coincide. ∎

If $\Gamma=\cup_{i\in I}\Gamma_{i}$ is a disjoint union of full subgraphs
which pairwise do not have any common edges and $f^{i}$ is a collection of
weight functions, then there is a unique weight function $f$ on $\Gamma$ whose
restriction to $\Gamma_{i}$ coincides with $f^{i}$ for every $i$. We will call
$f$ the _extension_ of the $\\{f^{i}:i\in I\\}$.

A full subgraph $\Gamma^{\prime}\subset\Gamma$ will be called path complete if
every oriented path in $\Gamma$ which starts from a vertex of
$\Gamma^{\prime}$ and ends at a vertex of $\Gamma^{\prime}$ is contained
entirely in $\Gamma$. For example, if $\Gamma=\lx@xy@svg{\hbox{\raise
0.0pt\hbox{\kern
5.5pt\hbox{\ignorespaces\ignorespaces\ignorespaces\hbox{\vtop{\kern
0.0pt\offinterlineskip\halign{\entry@#!@&&\entry<EMAIL_ADDRESS>0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{\hbox{\kern
59.5pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern
29.5pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise 0.0pt\hbox{$\textstyle{}$}}}}}}}{\hbox{\kern 59.5pt\raise
0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{2\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{\hbox{\kern
124.5pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern
94.5pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise 0.0pt\hbox{$\textstyle{}$}}}}}}}{\hbox{\kern 124.5pt\raise
0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{3}$}}}}}}}\ignorespaces}}}}\ignorespaces$, then the
full subgraph with vertices $1$ and $2$ is path complete while the full
subgraph with vertices $1$ and $3$ is not path complete.

Let $\Gamma^{\prime}$ be a path complete subgraph of $\Gamma$ and $f$ a weight
function. Let $f^{\prime}$ denote the restriction of $f$ to $\Gamma^{\prime}$
(then we have the corresponding representation $R_{f^{\prime}}$ of
$HK_{\Gamma^{\prime}}$). Consider the representation $R_{f}$ of $HK_{\Gamma}$
on $W=\bigoplus_{v\in\Gamma}\mathcal{R}v$. Let $\Gamma^{\prime\prime}$ be the
full subgraph of $\Gamma$ whose set of vertices consists of all vertices of
$\Gamma$ from which there is an oriented (but maybe trivial) path to a vertex
of $\Gamma^{\prime}$. Clearly, $\Gamma^{\prime}$ is a subgraph of
$\Gamma^{\prime\prime}$. Finally, let $\Gamma^{\prime\prime\prime}$ be the
full subgraph of $\Gamma$ whose set of vertices coincides with the set of all
vertices of $\Gamma^{\prime\prime}$ which do not belong to $\Gamma^{\prime}$.
Then both $X=\bigoplus_{v\in\Gamma^{\prime\prime}}\mathcal{R}v$ and
$Y=\bigoplus_{v\in\Gamma^{\prime\prime\prime}}\mathcal{R}v$ are invariant
under the action of $HK_{\Gamma}$ (the fact that $Y$ is invariant follows from
the path completeness of $\Gamma^{\prime}$). Let $\rho$ be the corresponding
representation of $HK_{\Gamma}$ on $X/Y$.

######  Proposition 4.3.

The representations $\rho$ and $R_{f^{\prime}}\circ p$ of $HK_{\Gamma}$ are
isomorphic.

###### Proof.

Define the map $\Phi:X/Y\to\bigoplus_{v\in\Gamma^{\prime}}\mathcal{R}v$ as the
unique $\mathcal{R}$-linear map which sends $v+Y$ for $v\in
V(\Gamma^{\prime})$ to $v$. This is obviously linear and bijective. The fact
that it is a homomorphism of $HK_{\Gamma}$-modules follows directly from the
definitions. ∎

This theorem says that, for every word $\mathbf{w}\in(V(\Gamma))^{*}$, the
minor of the matrix of $R_{f}([\mathbf{w}])$ corresponding to the basis
vectors $\\{v:v\in\Gamma^{\prime}\\}$ coincides with the matrix
$R_{f^{\prime}}\circ p([\mathbf{w}])$. This fails if $\Gamma^{\prime}$ is not
path complete. For example, if we let $\Gamma=\lx@xy@svg{\hbox{\raise
0.0pt\hbox{\kern
5.64294pt\hbox{\ignorespaces\ignorespaces\ignorespaces\hbox{\vtop{\kern
0.0pt\offinterlineskip\halign{\entry@#!@&&\entry<EMAIL_ADDRESS>0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{a\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{\hbox{\kern
29.64294pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern
29.64294pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise
0.0pt\hbox{$\textstyle{b\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{\hbox{\kern
63.9346pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern
63.9346pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise 0.0pt\hbox{$\textstyle{c}$}}}}}}}\ignorespaces}}}}\ignorespaces$
and $\Gamma^{\prime}$ be the full subgraph with vertices $a$ and $c$, then for
$\mathbf{w}=bc$ and $f\equiv 1$ we have $R_{1}([bc])(c)=a$ while
$R_{1^{\prime}}\circ p([bc])(c)=0$.

######  Proposition 4.4.

Assume that $\Gamma$ is a union of two full subgraphs, $\Gamma_{1}$ and
$\Gamma_{2}$ such that $V(\Gamma_{1})\cap V(\Gamma_{2})=\\{a\\}$ for some
$a\in\mathcal{S}_{\Gamma}$. Then the map $p=(p_{1},p_{2}):HK_{\Gamma}\to
HK_{\Gamma_{1}}\times HK_{\Gamma_{2}}$, where $p_{i}:HK_{\Gamma}\to
HK_{\Gamma_{i}}$, $i=1,2$, are projection morphisms, is injective.

###### Proof.

Let $\Gamma^{\prime}$ denote the full subgraph of $\Gamma$ with vertices
$V(\Gamma)\setminus\\{a\\}$ and define $\Gamma^{\prime}_{1}$ and
$\Gamma^{\prime}_{2}$ similarly. Since $a\in\mathcal{S}_{\Gamma}$, by Lemma
3.4 every element $[\mathbf{w}]\in HK_{\Gamma}$ contains at least one word
$\mathbf{w}^{\prime}$ which is multiplicity free with respect to $a$, i.e.
$\mathbf{w}^{\prime}=\mathbf{w}_{1}\alpha\mathbf{w}_{2}$ where
$\alpha\in\\{\varepsilon,a\\}$ and $\mathbf{w}_{1},\mathbf{w}_{2}\in
HK_{\Gamma^{\prime}}$. Moreover, $\Gamma^{\prime}$ is a disjoint union of
$\Gamma^{\prime}_{1}$ and $\Gamma^{\prime}_{2}$, so we may assume that
$\mathbf{w}_{1}=\mathbf{x}_{1}\mathbf{y}_{1},\mathbf{w}_{2}=\mathbf{x}_{2}\mathbf{y}_{2}$
for some $\mathbf{x}_{1},\mathbf{x}_{2}\in HK_{\Gamma^{\prime}_{1}}$ and
$\mathbf{y}_{1},\mathbf{y}_{2}\in HK_{\Gamma^{\prime}_{2}}$. We then have
$p([\mathbf{x}_{1}\mathbf{y}_{1}\alpha\mathbf{x}_{2}y_{2}])=([\mathbf{x}_{1}\alpha\mathbf{x}_{2}],[\mathbf{y}_{1}\alpha\mathbf{y}_{2}])$.

Let now $[\tilde{\mathbf{w}}]\in HK_{\Gamma}$ be such that
$p([\mathbf{w}])=p([\tilde{\mathbf{w}}])$ and assume that
$\tilde{\mathbf{w}}=\tilde{\mathbf{x}}_{1}\tilde{\mathbf{y}}_{1}\tilde{\alpha}\tilde{\mathbf{x}}_{2}\tilde{\mathbf{y}}_{2}$
is a decomposition as above. Then
$\tilde{\mathbf{x}}_{1}\alpha\tilde{\mathbf{x}}_{2}\sim\mathbf{x}_{1}\alpha\mathbf{x}_{2}$
and
$\tilde{\mathbf{y}}_{1}\alpha\tilde{\mathbf{y}}_{2}\sim\mathbf{y}_{1}\alpha\mathbf{y}_{2}$,
which, in particular, implies $\tilde{\alpha}=\alpha$. Note that all elements
from $HK_{\Gamma^{\prime}_{1}}$ commute with all elements from
$HK_{\Gamma^{\prime}_{2}}$ (since there are no edges between
$\Gamma^{\prime}_{1}$ and $\Gamma^{\prime}_{2}$). Therefore

$\tilde{\mathbf{x}}_{1}\tilde{\mathbf{y}}_{1}\tilde{\alpha}\tilde{\mathbf{x}}_{2}\tilde{\mathbf{y}}_{2}\sim\tilde{\mathbf{x}}_{1}\tilde{\mathbf{y}}_{1}\tilde{\alpha}\tilde{\mathbf{y}}_{2}\tilde{\mathbf{x}}_{2}\sim\tilde{\mathbf{x}}_{1}\mathbf{y}_{1}\alpha\mathbf{y}_{2}\tilde{\mathbf{x}}_{2}\sim\\\
\sim\mathbf{y}_{1}\tilde{\mathbf{x}}_{1}\alpha\tilde{\mathbf{x}}_{2}\mathbf{y}_{2}=\mathbf{y}_{1}\tilde{\mathbf{x}}_{1}\tilde{\alpha}\tilde{\mathbf{x}}_{2}\mathbf{y}_{2}\sim\mathbf{y}_{1}\mathbf{x}_{1}\alpha\mathbf{x}_{2}\mathbf{y}_{2}\sim\mathbf{x}_{1}\mathbf{y}_{1}\alpha\mathbf{x}_{2}\mathbf{y}_{2}.$

Hence $\tilde{\mathbf{w}}\sim\mathbf{w}$ and the claim follows. ∎

######  Theorem 4.5.

Let $\Gamma$, $\Gamma_{1}$ and $\Gamma_{2}$ be as in Proposition 4.4. Let
$f_{1}$ and $f_{2}$ be weight functions for $\Gamma_{1}$ and $\Gamma_{2}$,
respectively and $f$ be the extension of $\\{f_{1},f_{2}\\}$ to $\Gamma$. Then
the representation $R_{f}$ of $HK_{\Gamma}$ is effective if and only if the
representations $R_{f_{1}}$ of $HK_{\Gamma_{1}}$ and $R_{f_{2}}$ of
$HK_{\Gamma_{2}}$ are effective.

###### Proof.

Let $\Gamma^{\prime}$, $\Gamma^{\prime}_{1}$ and $\Gamma^{\prime}_{2}$ be as
in the proof of Proposition 4.4. We start with the “only if” part. Both
$\Gamma_{1}$ and $\Gamma_{2}$ are path complete, which implies that

$R_{f}[\mathbf{w}](v)=\begin{cases}R_{f_{i}}p_{i}[\mathbf{w}](v),&\text{ if
}v\in\Gamma_{i}^{\prime}\\\
R_{f_{1}}p_{1}[\mathbf{w}](a)+R_{f_{2}}p_{2}[\mathbf{w}](a),&\text{ if
}v=a\text{ and }a\in\mathfrak{c}[\mathbf{w}]\\\ 0&\text{otherwise}\end{cases}$

Now assume that $R_{f_{1}}$ is noneffective, i.e. there exists
$[\mathbf{w}_{1}]\neq[\mathbf{w}_{2}]\in HK_{\Gamma_{2}}$ such that
$R_{f_{1}}[\mathbf{w}_{1}]=R_{f_{1}}[\mathbf{w}_{2}]$. Then
$p_{2}[\mathbf{w}_{1}]=p_{2}[\mathbf{w}_{2}](=[a]\text{ or }[\varepsilon])$,
and

$R_{f}[\mathbf{w}_{1}](v)=\begin{cases}R_{f_{1}}p_{1}[\mathbf{w}_{1}](v),&\text{
if }v\in\Gamma_{1}^{\prime}\\\ R_{f_{2}}p_{2}[\mathbf{w}_{1}](v),&\text{ if
}v\in\Gamma_{2}^{\prime}\\\
R_{f_{1}}p_{1}[\mathbf{w}_{1}](a)+R_{f_{2}}p_{2}[\mathbf{w}_{1}](a),&\text{ if
}v=a\text{ and }a\in\mathfrak{c}[\mathbf{w}]\\\
0&\text{otherwise}\end{cases}=$

The “if” part follows by combining Propositions 4.3 and 4.4 (note again that
both $\Gamma_{1}$ and $\Gamma_{2}$ are path connected in $\Gamma$). Assume
that the representations $R_{f_{1}}$ of $HK_{\Gamma_{1}}$ and $R_{f_{2}}$ of
$HK_{\Gamma_{2}}$ are effective and consider the representation $R_{f}$ of
$HK_{\Gamma}$. Let $[\mathbf{w}]\neq[\mathbf{w}^{\prime}]$ be two elements of
$HK_{\Gamma}$. Assume $R_{f}([\mathbf{w}])=R_{f}([\mathbf{w}^{\prime}])$. Then
Propositions 4.3 and the arguments from the first part of the proof imply that
$R_{f_{1}}(p_{1}([\mathbf{w}]))=R_{f_{1}}(p_{1}([\mathbf{w}^{\prime}]))$ and
$R_{f_{2}}(p_{2}([\mathbf{w}]))=R_{f_{2}}(p_{2}([\mathbf{w}^{\prime}]))$.
Since both $R_{f_{1}}$ and $R_{f_{2}}$ are effective, we get
$p_{1}([\mathbf{w}])=p_{1}([\mathbf{w}^{\prime}])$ and
$p_{2}([\mathbf{w}])=p_{2}([\mathbf{w}^{\prime}])$. Now from Proposition 4.4
we get $[\mathbf{w}]=[\mathbf{w}^{\prime}]$, a contradiction. The claim
follows. ∎

This statement can now be iterated as follows. Assume that $\Gamma$ is a union
of full subgraphs, $\displaystyle\Gamma=\bigcup_{i=1}^{n}\Gamma_{i}$, where
$n>1$, such that each pair of different subgraphs does not have any common
edges and, moreover, we assume that for every $k=2,3,\dots,n$ there is
$a_{k}\in\mathcal{S}_{\Gamma}$ such that

$V(\Gamma_{k})\cap\big{(}\bigcup_{i=1}^{k-1}V(\Gamma_{i})\big{)}=\\{a_{k}\\}.$

In this case we will say that $\Gamma$ satisfies the _gluing condition_.

For example, let $\Gamma$ be of type $A_{n}$. If we define $\Gamma_{i}$ to be
the maximal connected linearly ordered full subgraphs of $\Gamma$, then
$\Gamma$ satisfies the gluing condition with respect to these subgraphs as
illustrated below (here $\Gamma_{i}$ is a subgraph with vertices between
$a_{i}$ and $a_{i+1}$, where $a_{0}$ is the leftmost vertex and $a_{k+1}$ is
the rightmost vertex):

(4.1)
---
$\textstyle{\bullet\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\cdots\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{a_{2}}$$\textstyle{\cdots\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{a_{3}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\cdots\cdots\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{a_{k}}$$\textstyle{\cdots\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\bullet\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\Gamma_{1}}$$\textstyle{\Gamma_{2}}$$\textstyle{\cdots}$$\textstyle{\Gamma_{k}}$

This implies the following corollary which answers [3, Question 8].

######  Corollary 4.6.

Let $\Gamma$ be of type $A_{n}$. Then the representation $R_{1}$ of
$HK_{\Gamma}$ is effective.

###### Proof.

This follows from Theorem 4.5 and [3, Subsection 3.2] by induction on $n$ (the
parameter in (4.1)). ∎

As a byproduct of the proof of Proposition 4.4 we get formulas for certain
cardinalities. An element $[\mathbf{w}]$ is said to have _maximal content_ if
$\mathfrak{c}[\mathbf{w}]=V(\Gamma)$. The subsemigroup consisting of elements
with maximal content is denoted by $\mathfrak{m}(\Gamma)$.

######  Theorem 4.7.

Assume that $\displaystyle\Gamma=\bigcup_{i=1}^{k}\Gamma_{i}$ satisfies the
gluing condition. Then

$|\mathfrak{m}(\Gamma)|=\prod_{i=1}^{k}|\mathfrak{m}(\Gamma_{i})|.$

###### Proof.

By induction, it is enough to prove the claim for
$\Gamma=\Gamma_{1}\cup\Gamma_{2}$. All we need to show is that the restricted
map
$p:\mathfrak{m}(\Gamma)\to\mathfrak{m}(\Gamma_{1})\times\mathfrak{m}(\Gamma_{2})$
is a bijection. Since we know that it is injective (by Proposition 4.4), we
only have to establish its surjectivity. Let
$([\mathbf{x}],[\mathbf{y}])\in\mathfrak{m}(\Gamma_{1})\times\mathfrak{m}(\Gamma_{2})$.
By definition, $a\in\mathfrak{c}[\mathbf{x}]$ and
$a\in\mathfrak{c}[\mathbf{y}]$, so there are words
$\mathbf{x}\sim\mathbf{x}_{1}a\mathbf{x}_{2},\mathbf{y}\sim\mathbf{y}_{1}a\mathbf{y}_{2}$
which are multiplicity free with respect to $a$. Then
$[\mathbf{x}_{1}\mathbf{y}_{1}a\mathbf{x}_{2}\mathbf{y}_{2}]$ is the preimage
of $([\mathbf{x}],[\mathbf{y}])$. The claim follows. ∎

The Catalan numbers $C_{n}=\frac{1}{n+1}{\binom{2n}{n}}$ are the cardinalities
of the HK-monoids of linearly ordered graphs, see [3, Theorem 1(vi)]. They can
also be used to calculate the cardinality of any HK-monoid of type $A_{n}$.

Let $\displaystyle\Gamma=\bigcup_{i=1}^{k}\Gamma_{i}$ be a graph of type
$A_{n}$ as in (4.1) or its opposite. For a subset $Q\subset\\{2,3,\cdots,k\\}$
and $i\in\\{2,3,\cdots,k-1\\}$ set

$\delta_{i}(Q)=\begin{cases}1,&\text{ if }a_{i}\in Q;\\\
0,&\text{otherwise};\end{cases}$
$c_{i}(Q)=\begin{cases}C_{l_{i}-1},&\delta_{i-1}(Q)=\delta_{i}(Q)=0;\\\
C_{l_{i}}-C_{l_{i}-1},&\delta_{i-1}(Q)+\delta_{i}(Q)=1;\\\
C_{l_{i}+1}-2C_{l_{i}}+C_{l_{i}-1},&\delta_{i-1}(Q)=\delta_{i}(Q)=1;\end{cases}$
$c_{1}(Q)=\begin{cases}C_{l_{1}},&\delta_{2}(Q)=0;\\\
C_{l_{1}+1}-C_{l_{1}},&\delta_{2}(Q)=1;\end{cases}\quad
c_{k}(Q)=\begin{cases}C_{l_{k}},&\delta_{k}(Q)=0;\\\
C_{l_{k}+1}-C_{l_{1}},&\delta_{k}(Q)=1.\end{cases}$

######  Corollary 4.8.

Let $\Gamma$ be as above. Then we have

  1. (i)

$\displaystyle|\mathfrak{m}(\Gamma)|=\prod_{i=1}^{k}C_{l_{i}}$,

  2. (ii)

$\displaystyle|HK_{\Gamma}|=\sum_{Q\subset\underline{k}\setminus\\{1\\}}\prod_{i=1}^{k}c_{i}(Q)$,

  3. (iii)

if $\Gamma=\mathcal{S}_{\Gamma}$, that is,

$\Gamma=a\rightarrow b\leftarrow c\rightarrow d\leftarrow\cdots x\quad\text{
or }\quad\Gamma=a\leftarrow b\rightarrow c\leftarrow d\rightarrow\cdots x,$

then $|HK_{\Gamma}|=F_{2n+1}$ is the $(2n+1)$-th Fibonacci number (where
$F_{1}=F_{2}=1)$.

###### Proof.

To prove the first claim we need to know $\mathfrak{m}(\Gamma_{i})$ and then
apply Theorem 4.7. Since $\Gamma_{i}$ is linearly ordered, the elements of
$HK_{\Gamma_{i}}$ are in bijection with order preserving and order decreasing
transformations on a set with $l_{i}+1$ elements, see [3, Theorem 1(vii)].
This bijection restricts to a bijection between $\mathfrak{m}(\Gamma_{i})$ and
transformations $\tau$ such that $\tau(j)<j$ for all $j\neq 1$. Changing $j$
in the domain to $j-1$ gives a bijection between $\mathfrak{m}(\Gamma_{i})$
with order preserving and order decreasing transformations on a set with
$l_{i}$ elements and hence $|\mathfrak{m}(\Gamma_{i})|=C_{l_{i}}$ by [3,
Theorem 1(vi) and (vii)].

For the second claim we have to work more. Assume that
$\Gamma=\Gamma_{1}\cup\Gamma_{2}$ satisfies the gluing condition with
$a\in\mathcal{S}_{\Gamma}$ as the common vertex. Then $HK_{\Gamma}$ splits
into two subsets (in fact subsemigroups) $A_{\Gamma}:=\\{[\mathbf{w}]\in
HK_{\Gamma}|a\in\mathfrak{c}[\mathbf{w}]\\}$ and
$B_{\Gamma}:=\\{[\mathbf{w}]\in
HK_{\Gamma}|a\not\in\mathfrak{c}[\mathbf{w}]\\}$. Similarly,
$HK_{\Gamma_{i}}=A_{\Gamma_{i}}\cup B_{\Gamma_{i}}$ for $i=1,2$. The function
$p$ in Proposition 4.4 restricts to bijections

$p:A_{\Gamma}\to A_{\Gamma_{1}}\times A_{\Gamma_{2}}\quad\text{ and }\quad
p:B_{\Gamma}\to B_{\Gamma_{1}}\times B_{\Gamma_{2}}.$

By the multiplicative principle we have
$|A_{\Gamma}|=|A_{\Gamma_{1}}|\cdot|A_{\Gamma_{2}}|$ and
$|B_{\Gamma}|=|B_{\Gamma_{1}}|\cdot|B_{\Gamma_{2}}|$.

For $Q\subset\\{a_{2},a_{3},\dots,a_{k}\\}$ and $i=2,\dots,k-1$ define

$X_{i}(Q):=\\{[\mathbf{w}]\in
HK_{\Gamma_{i}}:\mathfrak{c}([\mathbf{w}])\cap\\{a_{i},a_{i+1}\\}=A\cap\\{a_{i},a_{i+1}\\}\\}$

and set

$\displaystyle X_{1}(Q):=\\{[\mathbf{w}]\in
HK_{\Gamma_{1}}:\mathfrak{c}([\mathbf{w}])\cap\\{a_{1}\\}=A\cap\\{a_{1}\\}\\}$
$\displaystyle X_{k}(Q):=\\{[\mathbf{w}]\in
HK_{\Gamma_{k}}:\mathfrak{c}([\mathbf{w}])\cap\\{a_{k}\\}=A\cap\\{a_{k}\\}\\}.$

The the above discussion implies

(4.2)
$|HK_{\Gamma}|=\sum_{Q\subset\underline{k}\setminus\\{1\\}}\prod_{i=1}^{k}|X_{i}(Q)|.$

To compute cardinalities of $X_{i}(Q)$ we have to consider several case. We
start with the case $i\neq 1,k$.

  1. (1)

Assume that $i\not\in Q$ and $i+1\not\in Q$. If
$a_{i},a_{i+1}\not\in\mathfrak{c}[\mathbf{w}_{i}]$, then $[\mathbf{w}_{i}]$
can be thought of as living in the smaller HK-monoid
$HK_{\Gamma_{i}\setminus\\{a_{i},a_{i+1}\\}}$, and vice versa. Since
$\Gamma_{i}$ was assumed to be linearly ordered, it will be the case for
$\Gamma_{i}\setminus\\{a_{i},a_{i+1}\\}$ as well. Note that all $\Gamma_{i}$
have length $l_{i}\geq 2$ (if $\Gamma$ has at least two vertices). Therefore
$|HK_{\Gamma_{i}\setminus\\{a_{i},a_{i+1}\\}}|=C_{l_{i}-1}$.

  2. (2)

Assume that exactly one of $i,i+1$ is in $Q$. Without loss of generality
assume $i\in A$. Similarly as above we count the number of elements that _do
not_ contain $a_{i+1}$. That cardinality is $C_{l_{i}}$. However, we need to
exclude the elements that do not contain $a_{i}$, leaving us with exactly
$C_{l_{i}}-C_{l_{i}-1}$.

  3. (3)

If none of $i,i+1$ is in $Q$, we use the inclusion exclusion formula to get
$C_{l_{i}+1}-2(C_{l_{i}}-C_{l_{i}-1})-C_{l_{i}-1}=C_{l_{i}+1}-C_{l_{i}}+C_{l_{i}-1}$
elements.

When $i=1$ or $i=k$, we get the following two cases:

  1. (1)

Elements that do not contain $a=a_{2}$ or $a_{k}$. There are $C_{l_{i}}$ such
elements.

  2. (2)

Elements that do contain $a$. By exclusion there are $C_{l_{i}+1}-C_{l_{i}}$
such elements.

Now the second claim of our theorem follows from (4.2) and the definition of
$c_{i}(A)$.

We will prove the last claim by showing that it satisfies the same recursion
formula as the odd Fibonacci numbers and has the same initial values. Note
that if the number of vertices $n$ is fixed there are only two possibilities
for a graph of type $A_{n}$ to have alternating sinks or sources (the first
vertex can either be a sink or a source). However, these graphs are opposite
to each other, so the cardinalities of the corresponding HK-monoids have to
agree by [3, Theorem 1(v)]. Let $\mathcal{A}_{n}$ be the graph of type $A_{n}$
with alternating sinks and sources whose vertices are $v_{i}$,
$i\in\underline{n}$, and we assume that $v_{1}$ is a source. Let
$f_{n}=|HK_{\mathcal{A}_{n}}|$. The first two $\mathcal{A}_{n}$ are
$\mathcal{A}_{0}=$ the empty graph, and $\mathcal{A}_{1}=v_{1}$. This gives
$f_{0}=|\\{\varepsilon\\}|=1=F_{2\cdot 0+1}$ and
$f_{1}=|\\{\varepsilon,[v_{1}]\\}|=2=F_{2\cdot 1+1}$. The Fibonacci numbers
satisfy the recursion formula

$F_{n+2}=F_{n+1}+F_{n}=2F_{n}+F_{n-1}=3F_{n}-F_{n-2}.$

Thus we want to show that $f_{n+1}=3f_{n}-f_{n-1}$. We can separate the
elements of $HK_{\mathcal{A}_{n+1}}$ into two cases. Either the content of an
element contains $v_{n}$ or it does not.

  1. (1)

Assume $v_{n}\not\in\mathfrak{c}[\mathbf{w}]$, then $[\mathbf{w}]$ equals an
element from $HK_{\mathcal{A}_{n-1}}$ multiplied with either $\varepsilon$ or
$v_{n+1}$. Thus there are $f_{n-1}\cdot 2=2f_{n-1}$ such elements.

  2. (2)

Assume $v_{n}\in\mathfrak{c}[\mathbf{w}]$, then $[\mathbf{w}]$ is a product of
an element from $HK_{\mathcal{A}_{n}}$ _containing_ $v_{n}$ with an element
from $HK_{\mathcal{B}}$ _containing_ $v_{n}$, where $\mathcal{B}$ is the full
subgraph of $\mathcal{A}_{n+1}$ with vertices $\\{v_{n},v_{n+1}\\}$. We have
$(f_{n}-f_{n-1})\cdot 3=3f_{n}-3f_{n-1}$ such elements.

This implies $f_{n+1}=3f_{n}-f_{n-1}$ and completes the proof of our theorem.
∎

The sequence $F_{2n+1}$ was guessed with the help of [1] and has been found
independently by Grensing [4].

######  Corollary 4.9.

Let $\Gamma$ be of type $A_{n}$. Then the number of multiplicity free elements
in $HK_{\Gamma}$ is the Fibonacci number $F_{2n+1}$. In particular, it does
not depend on the orientation of edges in $\Gamma$.

###### Proof.

Lemma 3.4 tells us that every element $[\mathbf{w}]$ contains a word
$\mathbf{w}^{\prime}$ which is multiplicity free _with respect to every source
and sink_. Since $\mathcal{A}_{n}$ has only sources and sinks every element of
$HK_{\mathcal{A}_{n}}$ is in fact multiplicity free. Since
$|HK_{\mathcal{A}_{n}}|=F_{2n+1}$ by the previous theorem, we need to show
that there is a bijection between multiplicity free elements of $HK_{\Gamma}$
and $HK_{\mathcal{A}_{n}}$. Let $\mathbf{w}$ be a multiplicity free word and
assume that $\Gamma$ is enumerated canonically. Then for each
$i\in\underline{n-1}$ exactly one of the following holds.

  1. (1)

$v_{i+1}\not\in\mathfrak{c}[\mathbf{w}]$.

  2. (2)

$v_{i}\not\in\mathfrak{c}[\mathbf{w}]$ but
$v_{i+1}\in\mathfrak{c}[\mathbf{w}]$.

  3. (3)

Both $v_{i},v_{i+1}\in\mathfrak{c}[\mathbf{w}]$ and $v_{i}$ appears before
$v_{i+1}$ in $\mathbf{w}$.

  4. (4)

Both $v_{i},v_{i+1}\in\mathfrak{c}[\mathbf{w}]$ and $v_{i+1}$ appears before
$v_{i}$ in $\mathbf{w}$.

We claim that these properties do not depend on the choice of a _multiplicity
free_ element $\mathbf{w}^{\prime}\in[\mathbf{w}]$. For the first two
properties the claim is obvious. Let $\Gamma_{i}$ be the complete subgraph of
$\Gamma$ whose vertices are $v_{i},v_{i+1}$, and consider the map
$p:\big{(}V(\Gamma)\big{)}^{*}\to\big{(}V(\Gamma_{i})\big{)}^{*}$ defined by
deletion of vertices not in $\Gamma_{i}$. It is clear that

  1. (a)

If $\mathbf{w}$ is multiplicity free, then so is $p(\mathbf{w})$.

  2. (b)

If $\mathbf{w}\sim\mathbf{w}^{\prime}$ then $p(\mathbf{w})\sim
p(\mathbf{w}^{\prime})$.

This means that under $p$ all multiplicity free words that contain both
$v_{i}$ and $v_{i+1}$ are mapped to $v_{i}v_{i+1}$ or $v_{i+1}v_{i}$. However,
there is an edge between $v_{i}$ and $v_{i+1}$, so $v_{i}v_{i+1}\not\sim
v_{i+1}v_{i}$, proving our claim for the third and the fourth properties.

We will show that multiplicity free elements are uniquely defined by the
relative positions of $v_{i}$ and $v_{i+1}$ for each $i$. Set

$\mathbf{w}_{1}=\begin{cases}v_{1}&\text{ if
}v_{1}\in\mathfrak{c}[\mathbf{w}];\\\ \varepsilon&\text{ if
}v_{1}\not\in\mathfrak{c}[w];\end{cases}$
$\mathbf{w}_{i+1}=\begin{cases}\mathbf{w}_{i}&\text{ if
}v_{i+1}\not\in\mathfrak{c}[\mathbf{w}];\\\ \mathbf{w}_{i}v_{i+1}&\text{ if
}v_{i}\not\in\mathfrak{c}[\mathbf{w}]\text{ or }v_{i}\text{ appears to the
left of }v_{i+1}\text{ in }\mathbf{w};\\\ v_{i+1}\mathbf{w}&\text{ if
}v_{i+1}\text{ appears to the left of }v_{i}\text{ in }\mathbf{w}.\end{cases}$

Let $\mathfrak{M}\subset HK_{\Gamma}$ denote the set of all multiplicity free
elements and define the map $\phi:\mathfrak{M}\to HK_{\mathcal{A}_{n}}$ by
$\phi([\mathbf{w}])=[\mathbf{w}_{n}]$, where $\mathbf{w}$ is multiplicity free
and $\mathbf{w}_{n}$ is defined from $\mathbf{w}$ by the above above. Note
that $\phi$ is well-defined because it only uses invariant properties. Since
$\phi:HK_{\mathcal{A}_{n}}\to HK_{\mathcal{A}_{n}}$ is the identity and the
multiplicity free _words_ are the same for all $\Gamma$ (over the same
vertices) it follows that $\phi$ is surjective for any domain. To show that
$\phi$ is injective it suffices to show that $\mathbf{w}\sim\mathbf{w}_{n}$
(in $HK_{\Gamma}$) for each multiplicity free $\mathbf{w}$. We show this by
deforming $\mathbf{w}$ into $\mathbf{w}_{n}$. Clearly $\mathbf{w}$ can be
factorized as $\mathbf{w}=\mathbf{x}_{1}\mathbf{w}_{1}\mathbf{y}_{1}$, where
$v_{1}\not\in\mathfrak{c}([\mathbf{x}_{1}]),\mathfrak{c}([\mathbf{y}_{1}])$.
Assume that $\mathbf{w}\sim\mathbf{x}_{i}\mathbf{w}_{i}\mathbf{y}_{i}$ where
$\\{v_{1},\cdots,v_{i}\\}\cap\big{(}\mathfrak{c}([\mathbf{x}_{i}])\cup\mathfrak{c}([\mathbf{y}_{i}])\big{)}=\emptyset$.
Note that $\mathbf{w}_{i}$ commutes with every vertex _except_ $v_{i+1}$.

  1. (1)

If $v_{i+1}\not\in\mathfrak{c}([\mathbf{w}])$, then
$\mathbf{w}_{i+1}=\mathbf{w}_{i}$.

  2. (2)

If $v_{i}\not\in\mathfrak{c}([\mathbf{w}])$ but
$v_{i+1}\in\mathfrak{c}([\mathbf{w}])$ then $\mathbf{w}_{i}$ commutes with
every vertex and we may move it so that it ends up just to the left of
$v_{i+1}$.

  3. (3)

If both $v_{i},v_{i+1}\in\mathfrak{c}([\mathbf{w}])$ and $v_{i}$ appears
before $v_{i+1}$ in $\mathbf{w}$ then $\mathbf{w}_{i}$ commutes with every
vertex in $\mathbf{y}_{i}$ preceding $v_{i+1}$. Hence we may move
$\mathbf{w}_{i}$ so that it ends up just to the left of $v_{i+1}$.

  4. (4)

If both $v_{i},v_{i+1}\in\mathfrak{c}([\mathbf{w}])$ and $v_{i+1}$ appears
before $v_{i}$ in $\mathbf{w}$ we move $\mathbf{w}_{i}$ so that it ends up
just to the right of $v_{i+1}$.

In all cases we find that

$\mathbf{w}\sim\mathbf{x}_{i}\mathbf{w}_{i}\mathbf{y}_{i}\sim\mathbf{x}_{i+1}\mathbf{w}_{i+1}\mathbf{y}_{i+1}$

for some $\mathbf{x}_{i+1}$ and $\mathbf{y}_{i+1}$ such that
$\\{v_{1},\cdots,v_{i},v_{i+1}\\}\cap\big{(}\mathfrak{c}([\mathbf{x}_{i+1}])\cup\mathfrak{c}([\mathbf{y}_{i+1}])\big{)}=\emptyset$.
Proceeding inductively, we get
$\mathbf{w}\sim\mathbf{x}_{n}\mathbf{w}_{n}\mathbf{y}_{n}$ such that
$\mathfrak{c}([\mathbf{x}_{n}])=\mathfrak{c}([\mathbf{y}_{n}])=\emptyset$, so
$\mathbf{w}\sim\mathbf{w}_{n}$. ∎

To illustrate the process that turns $\mathbf{w}$ into $\mathbf{w}_{n}$ let
$\mathbf{w}=cfadb$ (here the order of letters is
$a=v_{1},b=v_{2},c=v_{3},d=v_{4},e=v_{5},f=v_{6}$).

$\mathbf{x}_{1}\mathbf{w}_{1}\mathbf{y}_{1}=(cf)(a)(db)$ | $\mathbf{x}_{2}\mathbf{w}_{2}\mathbf{y}_{2}=(cfd)(ab)()$ | $\mathbf{x}_{3}\mathbf{w}_{3}\mathbf{y}_{3}=()(cab)(fd)$
---|---|---
$\mathbf{x}_{4}\mathbf{w}_{4}\mathbf{y}_{4}=(f)(cabd)()$ | $\mathbf{x}_{5}\mathbf{w}_{5}\mathbf{y}_{5}=(f)(cabd)()$ | $\mathbf{x}_{6}\mathbf{w}_{6}\mathbf{y}_{6}=()(cabdf)()$

As a consequence of the previous corollary we have $F_{2n+1}\leq|HK_{\Gamma}|$
for any $\Gamma$. We also have $|HK_{\Gamma}|\leq C_{n+1}$ by [3, Theorem
1(vi)]. It seems plausible that more sources and sinks corresponds to a
smaller monoid. The following theorem makes this idea more precise.

######  Theorem 4.10.

Let $\Gamma=\Gamma_{1}\cup\Gamma_{2}$ be an edge disjoint union of graphs such
that $\Gamma_{1}\cap\Gamma_{2}=\\{a\\}$ is a source or a sink. Let
$\overleftarrow{\Gamma_{2}}$ be the graph obtained from $\Gamma_{2}$ by
reversing the direction of all edges and let
$\tilde{\Gamma}=\Gamma_{1}\cup\overleftarrow{\Gamma_{2}}$. Then
$|HK_{\Gamma}|\leq|HK_{\tilde{\Gamma}}|$ and the equality holds if and only if
$a$ is isolated in at least one of $\Gamma_{1},\Gamma_{2}$.

###### Proof.

For any HK-monoid $HK_{\Gamma^{\prime}}$ and $a\in V(\Gamma^{\prime})$ define

$HK_{\Gamma^{\prime}}^{0}=\\{[\mathbf{w}]\in
HK_{\Gamma^{\prime}}|a\not\in\mathfrak{c}[\mathbf{w}]\\},$
$HK_{\Gamma^{\prime}}^{1}=\\{[\mathbf{w}]\in
HK_{\Gamma^{\prime}}|a\in\mathfrak{c}[\mathbf{w}]\text{ and
}[\mathbf{w}]\text{ is multiplicity free with respect to }a\\},$
$HK_{\Gamma^{\prime}}^{2}=\\{[\mathbf{w}]\in
HK_{\Gamma^{\prime}}|[\mathbf{w}]\text{ is not multiplicity free with respect
to }a\\}.$

Clearly $HK_{\Gamma^{\prime}}$ is a disjoint union of
$HK_{\Gamma^{\prime}}^{0}$, $HK_{\Gamma^{\prime}}^{1}$ and
$HK_{\Gamma^{\prime}}^{2}$.

Because $|HK_{\Gamma^{\prime}}|=|HK_{\overleftarrow{\Gamma^{\prime}}}|$ by [3,
Theorem 1(v)], it follows that

$|HK_{\Gamma}^{0}|=|HK_{\Gamma_{1}\setminus\\{a\\}}||HK_{\Gamma_{2}\setminus\\{a\\}}|=|HK_{\Gamma_{1}\setminus\\{a\\}}||HK_{\overleftarrow{\Gamma_{2}\setminus\\{a\\}}}|=|HK_{\tilde{\Gamma}}^{0}|.$

To see that $|HK_{\Gamma}^{1}|=|HK_{\tilde{\Gamma}}^{1}|$ observe that any
element $[\mathbf{w}]$ in $HK_{\Gamma}^{1}$ has a word of the form
$\mathbf{w}=\mathbf{x}_{1}\mathbf{y}_{1}a\mathbf{x}_{2}\mathbf{y}_{2}$ for
some $\mathbf{x}_{1},\mathbf{x}_{2}\in
HK_{\Gamma_{1}\setminus\\{a\\}},\mathbf{y}_{1},\mathbf{y}_{2}\in
HK_{\Gamma_{2}\setminus\\{a\\}}$. Similarly for $HK_{\tilde{\Gamma}^{1}}$.
This is true because there are no edges between $\Gamma_{1}\setminus\\{a\\}$
and $\Gamma_{2}\setminus\\{a\\}$. Let $\phi:HK_{\Gamma}^{1}\to
HK_{\tilde{\Gamma}}^{1}$ be defined by
$\phi[\mathbf{x}_{1}\mathbf{y}_{1}a\mathbf{x}_{2}\mathbf{y}_{2}]=\mathbf{x}_{1}\overleftarrow{\mathbf{y}_{2}}a\mathbf{x}_{2}\overleftarrow{\mathbf{y}_{1}}$,
where $\overleftarrow{\mathbf{y}}$ is the reverse of $\mathbf{y}$. Note that
$\phi$ is a bijection if it is well-defined. To see that it is well-defined,
assume
$\mathbf{x}_{1}\mathbf{y}_{1}a\mathbf{x}_{2}\mathbf{y}_{2}\sim\mathbf{x}_{1}^{\prime}\mathbf{y}_{1}^{\prime}a\mathbf{x}_{2}^{\prime}\mathbf{y}_{2}^{\prime}$.
By taking the right projection morphisms (onto $HK_{\Gamma_{1}}$ and
$HK_{\Gamma_{2}}$, respectively) we obtain
$\mathbf{x}_{1}a\mathbf{x}_{2}\sim\mathbf{x}_{1}^{\prime}a\mathbf{x}_{2}^{\prime}$
and
$\mathbf{y}_{1}a\mathbf{y}_{2}\sim\mathbf{y}_{1}^{\prime}a\mathbf{y}_{2}^{\prime}$.
Note that
$\mathbf{y}\sim\mathbf{y}^{\prime}\iff\overleftarrow{\mathbf{y}}\sim\overleftarrow{\mathbf{y}^{\prime}}$.
We have:

(4.3)
$\phi(\mathbf{w})=\phi(\mathbf{x}_{1}\mathbf{y}_{1}a\mathbf{x}_{2}\mathbf{y}_{2})=\mathbf{x}_{1}\overleftarrow{\mathbf{y}_{2}}a\mathbf{x}_{2}\overleftarrow{\mathbf{y}_{2}}\sim\mathbf{x}_{1}\overleftarrow{\mathbf{y}_{2}}a\overleftarrow{\mathbf{y}_{2}}\mathbf{x}_{2}=\mathbf{x}_{1}\overleftarrow{\mathbf{y}_{1}a\mathbf{y}_{2}}\mathbf{x}_{2}\sim\\\
\mathbf{x}_{1}\overleftarrow{\mathbf{y}_{1}^{\prime}a\mathbf{y}_{2}^{\prime}}\mathbf{x}_{2}=\mathbf{x}_{1}\overleftarrow{\mathbf{y}_{2}^{\prime}}a\overleftarrow{\mathbf{y}_{2}^{\prime}}\mathbf{x}_{2}\sim\overleftarrow{\mathbf{y}_{2}^{\prime}}\mathbf{x}_{1}a\mathbf{x}_{2}\overleftarrow{\mathbf{y}_{2}^{\prime}}\sim\overleftarrow{\mathbf{y}_{2}^{\prime}}\mathbf{x}_{1}^{\prime}a\mathbf{x}_{2}^{\prime}\overleftarrow{\mathbf{y}_{2}^{\prime}}\sim\mathbf{x}_{1}^{\prime}\overleftarrow{\mathbf{y}_{2}^{\prime}}a\mathbf{x}_{2}^{\prime}\overleftarrow{\mathbf{y}_{2}^{\prime}}=\phi(\mathbf{w}^{\prime}).$

This implies that $|HK_{\Gamma}^{1}|=|HK_{\tilde{\Gamma}}^{1}|$.

Finally, because $a\in\Gamma$ is a source or a sink, the set $HK_{\Gamma}^{2}$
is empty. Thus we have established the inequality
$|HK_{\Gamma}|\leq|HK_{\tilde{\Gamma}}|$. This inequality is an equality
precisely if and only if $HK_{\tilde{\Gamma}}^{2}$ is empty. If there exist
$b,c$ such that $b\to a\to c$, then $[abca]\in HK_{\tilde{\Gamma}}^{2}$. This
can only happen if $a$ is connected to some $b^{\prime}\in HK_{\Gamma_{1}}$
and some $c^{\prime}\in HK_{\Gamma_{2}}$. On the other hand, if $a$ is not
connected to any other vertex in either $\Gamma_{1}$ or $\Gamma_{2}$, then $a$
is a source or a sink in $\tilde{\Gamma}$ as well, implying that
$HK_{\tilde{\Gamma}}^{2}$ is empty. This completes the proof. ∎

##  5\. Limits of the method

The main idea of taking smaller graphs, whose HK-monoids have known effective
representations, and gluing them together has a few limitations

  1. (1)

We only know effective representations for a few types of graphs _that
themselves are not reached in this way_. So far we have the linearly ordered
graphs of type $A_{n}$ and the graphs $\kappa_{n}$ of the Kiselman monoids.

  2. (2)

When we glue two subgraphs together we are limited to gluing sinks to sinks
and sources to sources.

  3. (3)

When we glue two subgraphs together the intersection must consist of one
vertex. In particular this prevents us from forming loops.

We may enlarge the set of “building blocks” by considering the following
family of graphs:

|
---|---
$\textstyle{Z_{n}=}$$\textstyle{a\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\cdots}$$\textstyle{v_{3}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{v_{4}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\cdots\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\cdots}$$\textstyle{v_{n-1}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{v_{n}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{b}$

We can get a complete description of the elements in $HK_{Z_{n}}$ by observing
that, since $a$ is a source, any element contains a word with at most one $a$.
The subwords before and after $a$ do not contain $a$ and could therefore be
thought of as living in $\big{(}V(Z_{n}\setminus\\{a\\})\big{)}^{*}$. However,
in $Z_{n}\setminus\\{a\\}$ every vertex is a sink or a source, so we may
assume that there is at most one $v_{i}$ on each side of $a$. A similar
argument holds for $b$. Thus each element $[\mathbf{w}]$ in $HK_{Z_{n}}$
contains a word $\mathbf{w}^{\prime}$ which falls into exactly one of the
following types:

  1. (1)

We have $a,b\not\in\mathfrak{c}(\mathbf{w}^{\prime})$ and
$\mathbf{w}^{\prime}$ multiplicity free. Since all $v_{i}$ commute with each
other we may take $\mathbf{w}^{\prime}=v_{i_{1}}v_{i_{1}}\cdots v_{i_{j}}$
with $i_{1}<i_{2}<\cdots<i_{j}$.

  2. (2)

We have
$a\in\mathfrak{c}[\mathbf{w}^{\prime}],b\not\in\mathfrak{c}[\mathbf{w}^{\prime}]$
and $\mathbf{w}^{\prime}=\mathbf{w}_{1}a\mathbf{w}_{2}$ is multiplicity free.
Similarly as in the first case, $\mathbf{w}_{1},\mathbf{w}_{2}$ may be taken
with internally increasing order.

  3. (3)

We have
$a\not\in\mathfrak{c}[\mathbf{w}^{\prime}],b\in\mathfrak{c}[\mathbf{w}^{\prime}]$
and $\mathbf{w}^{\prime}=\mathbf{w}_{1}b\mathbf{w}_{2}$ is multiplicity free.
As in the second case, $\mathbf{w}_{1},\mathbf{w}_{2}$ may be taken with
internally increasing order.

  4. (4)

We have $a,b\in\mathfrak{c}[\mathbf{w}^{\prime}]$ and
$\mathbf{w}^{\prime}=\mathbf{w}_{1}a\mathbf{w}_{2}b\mathbf{w}_{3}$. We may
take $\mathbf{w}^{\prime}$ such that
$\mathfrak{c}(w_{1})\cap\mathfrak{c}(w_{2})=\emptyset$ and
$\mathfrak{c}(w_{2})\cap\mathfrak{c}(w_{3})=\emptyset$ and
$\mathbf{w}_{1},\mathbf{w}_{2}$ and $\mathbf{w}_{3}$ are internally
increasing.

  5. (5)

We have $a,b\in\mathfrak{c}[\mathbf{w}^{\prime}]$ and
$\mathbf{w}^{\prime}=\mathbf{w}_{1}b\mathbf{w}_{2}a\mathbf{w}_{3}$ with the
same restrictions as in the previous case and, additionally,
$\mathbf{w}_{2}\neq\varepsilon$.

The proof of the next theorem shows that all these elements are, in fact,
different.

######  Theorem 5.1.

Let $\Gamma=Z_{n}$ and let $f$ be defined by $f_{av_{i}}=1,f_{v_{i}b}=2^{i}$
for all $i$. Then $R_{f}$ is an effective representation of $HK_{Z_{n}}$.

###### Proof.

First we note that $R_{f}([\mathbf{w}])(x)=x$ if and only if
$x\not\in\mathfrak{c}(\mathbf{w})$. This means that $R_{f}$ distinguishes
elements with different contents from each other. Assume first that the
content of $\mathbf{w}$ satisfies $a\not\in\mathfrak{c}(\mathbf{w})$ or
$b\not\in\mathfrak{c}(\mathbf{w})$. Then $[\mathbf{w}]$ belongs to some
$HK_{\Gamma^{\prime}}$ for which $\Gamma^{\prime}$ is a path connected
subgraph of $\Gamma$ and is a finite edge-disjoint union of graphs of type
$A_{2}$. Since $\Gamma$ has no oriented cycles, there is an
$HK_{\Gamma^{\prime}}$-subquotient of $R_{f}$ isomorphic, as a vector space,
to $\oplus_{v\in V(\Gamma^{\prime})}\mathcal{R}v$ with the induced action
(i.e. everything outside this space is treated as zero). From the results of
the previous section it follows that the restriction of $R_{f}$ to the action
of $HK_{\Gamma^{\prime}}$ on $\oplus_{v\in V(\Gamma^{\prime})}\mathcal{R}v$ is
effective and hence separates different elements with content
$\mathfrak{c}(\mathbf{w})$.

If $a,b\in\mathfrak{c}(\mathbf{w})$ but some
$v_{i}\not\in\mathfrak{c}(\mathbf{w})$, then we can use induction on $n$.
Without loss of generality we may assume $i=n$. In this case $[\mathbf{w}]$
belongs to $HK_{Z_{n-1}}$. Considering the induced action of $HK_{Z_{n-1}}$ on
$\oplus_{v\in V(Z_{n-1})}\mathcal{R}v$ and taking the quotient modulo the
invariant subspace $\mathcal{R}v_{n}$, we may use the induction hypothesis and
conclude that $R_{f}$ separates elements with such content. Notre that the
basis of the induction is the case of a graph of type $A_{3}$ which is dealt
with using the results from the previous section.

Finally, it remains to show that $R_{f}$ separates elements of the maximal
content, that is elements described in the last two cases (4) and (5) before
the theorem with the condition
$\mathfrak{c}(\mathbf{w}_{1})\cup\mathfrak{c}(\mathbf{w}_{2})\cup\mathfrak{c}(\mathbf{w}_{3})=\\{v_{3},v_{4},\dots,v_{n}\\}$.

A direct computation shows that the element
$\mathbf{w}_{1}a\mathbf{w}_{2}b\mathbf{w}_{3}$ from (4) acts on the basis
elements of $\oplus_{v\in V(\Gamma)}\mathcal{R}v$ as follows:

$\displaystyle b\mapsto 0;\quad\quad
a\mapsto\sum_{v_{i}\not\in\mathfrak{c}(\mathbf{w}_{1})}f_{av_{i}}v_{i}+\sum_{v_{i}\in\mathfrak{c}(\mathbf{w}_{1})}f_{av_{i}}f_{v_{i}b}b;$
$\displaystyle\mathfrak{c}(\mathbf{w}_{3})\ni v_{i}\mapsto
0;\quad\quad\mathfrak{c}(\mathbf{w}_{2})\ni v_{i}\mapsto
f_{v_{i}b}b;\quad\quad\mathfrak{c}(\mathbf{w}_{1})\setminus\mathfrak{c}(\mathbf{w}_{3})\ni
v_{i}\mapsto f_{v_{i}b}b.$

Similarly, the element $\mathbf{w}_{1}b\mathbf{w}_{2}a\mathbf{w}_{3}$ from (5)
acts as follows:

$\displaystyle b\mapsto 0;\quad\quad
a\mapsto\sum_{v_{i}\not\in\mathfrak{c}(\mathbf{w}_{1})\setminus\mathfrak{c}(\mathbf{w}_{2})}f_{av_{i}}v_{i}+\sum_{v_{i}\in\mathfrak{c}(\mathbf{w}_{1})\setminus\mathfrak{c}(\mathbf{w}_{2})}f_{av_{i}}f_{v_{i}b}b;$
$\displaystyle\mathfrak{c}(\mathbf{w}_{3})\ni v_{i}\mapsto
0;\quad\quad\mathfrak{c}(\mathbf{w}_{2})\ni v_{i}\mapsto
0;\quad\quad\mathfrak{c}(\mathbf{w}_{1})\setminus\mathfrak{c}(\mathbf{w}_{3})\ni
v_{i}\mapsto f_{v_{i}b}b.$

Comparing these two formulae it is easy to see that different words act
differently, in particular, they define different elements in $HK_{Z_{n}}$. ∎

We can describe the graphs whose HK-monoids we have constructed effective
representations for. We do it in three steps.

  1. (1)

Pick a forest $\Gamma^{\prime}$ whose edges are undirected.

  2. (2)

Direct every edge such that every vertex in $\Gamma^{\prime}$ becomes either a
source or a sink. Call the resulting graph $\Gamma^{\prime\prime}$

  3. (3)

Replace every edge in $\Gamma^{\prime\prime}$ independently with one of the
following:

    1. (a)

a linearly ordered graph of type $A_{n},n\geq 1$,

    2. (b)

a "Kiselman graph" $\kappa_{n},n\geq 2$,

    3. (c)

or some $Z_{n}$ for $n\geq 4$,

matching source to source and sink to sink. Call the resulting graph $\Gamma$.

By choosing any weights on the linearly ordered parts, weights according to
[7] on the "Kiselman graph"-parts and weights according to the previous
theorem on the $Z_{n}$-parts one obtains an effective representation of
$HK_{\Gamma}$ over any ground ring $\mathcal{R}\supset\mathbb{Z}$.

######  Example.

A graph that we can reach with the three step algorithm

  1. (1)

Pick a forest:

|  |
---|---|---
$\textstyle{\bullet\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\bullet\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\bullet\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\bullet\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\bullet\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\bullet\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\bullet}$$\textstyle{\bullet}$$\textstyle{\bullet}$$\textstyle{\bullet}$

  2. (2)

Direct the edges so that vertices become _only_ sources and sinks:

|  |
---|---|---
$\textstyle{\bullet\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\bullet\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\bullet\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\bullet\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\bullet\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\bullet\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\bullet}$$\textstyle{\bullet}$$\textstyle{\bullet}$$\textstyle{\bullet}$

  3. (3)

Replace edges with linearly ordered $A_{n}$-graphs, graphs $\kappa_{n}$ or
graphs $Z_{n}$:

$\textstyle{\bullet\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\bullet\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\bullet\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\bullet\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\bullet\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\bullet\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\bullet\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\bullet\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\bullet\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\bullet\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\bullet\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\bullet\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\bullet}$$\textstyle{\bullet}$$\textstyle{\bullet}$$\textstyle{\bullet\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\bullet\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\bullet\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\bullet\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$

## References

  * [1] The on-line encyclopedia of integer sequences.
  * [2] R. Aragona and A. D’Andrea.  Hecke-kiselman monoids of small cardinality.  Semigroup Forum, 86(1):32–40, 2013.
  * [3] O. Ganyushkin and V. Mazorchuk.  On kiselman quotients of 0-hecke monoids.  International Electronic Journal of Algebra, 10:174–191, 2011.
  * [4] A.-L. Grensing.  Monoid algebras of projection functors.  Journal of Algebra, 369(1):16–41, 2012.
  * [5] A.-L. Grensing and V. Mazorchuk.  Categorification of the Catalan monoid.  Preprint arXiv:1211.2597.  Semigroup Forum (to appear).
  * [6] C. Kiselman.  A semigroup of operators in convexity theory.  Transactions of the American Mathematical Society, 354(5):2035–2053, 2002.
  * [7] G. Kudryavtseva and V. Mazorchuk.  On kiselman’s semigroup.  Yokohama Math. J., 55(1):21–46, 2009.
  * [8] V. Mazorchuk and B. Steinberg.  Effective dimension of finite semigroups.  Journal of Pure and Applied Algebra, 216(12):2737–3753, Dec. 2012\.
  * [9] A.-L. Paasch.  Monoidalgebren von Projektionsfunktoren.  PhD thesis, Bergischen Universität Wuppertal, 2011.