# The Gelfand–Kirillov dimension of Hecke–Kiselman algebras

Magdalena Wiertel

###### Abstract

Hecke–Kiselman algebras $A_{\Theta}$, over a field $k$, associated to finite
oriented graphs $\Theta$ are considered. It has been known that every such
algebra is an automaton algebra in the sense of Ufranovskii. In particular,
its Gelfand–Kirillov dimension is an integer if it is finite. In this paper, a
numerical invariant of the graph $\Theta$ that determines the dimension of
$A_{\Theta}$ is found. Namely, we prove that the Gelfand–Kirillov dimension of
$A_{\Theta}$ is the sum of the number of cyclic subgraphs of $\Theta$ and the
number of oriented paths of a special type in the graph, each counted certain
specific number of times.

2010 Mathematics Subject Classification: 16P90, 16S15, 16S36, 20M05, 20M25,
05C25.

Key words: Hecke–Kiselman algebra, monoid, Gelfand–Kirillov dimension, reduced
words, automaton algebra

##  1 Introduction

Let $\Theta=(V(\Theta),E(\Theta))$ be an oriented finite simple graph with $n$
vertices $x_{1},\ldots,x_{n}$. In [6] the Hecke–Kiselman monoid
$\operatorname{HK}_{\Theta}$ associated with $\Theta$ has been defined by the
following presentation.

  * (i)

$\operatorname{HK}_{\Theta}$ is generated by elements $x_{i}^{2}=x_{i}$, where
$1\leq i\leq n$,

  * (ii)

if the vertices $x_{i}$, $x_{j}$ are not connected in $\Theta$, then
$x_{i}x_{j}=x_{j}x_{i}$,

  * (iii)

if $x_{i}$, $x_{j}$ are connected by an arrow $x_{i}\to x_{j}$ in $\Theta$,
then $x_{i}x_{j}x_{i}=x_{j}x_{i}x_{j}=x_{i}x_{j}$.

By $k[\operatorname{HK}_{\Theta}]$ we mean the monoid algebra of
$\operatorname{HK}_{\Theta}$ over a field $k$. Since the ground field $k$ does
not play any role in our considerations we will denote this algebra by
$A_{\Theta}$.

Hecke–Kiselman monoids are natural quotients of $0$–Hecke monoids. The monoid
algebras of the latter monoids are specializations of famous Iwahori–Hecke
algebras, crucial in the representation theory of Coxeter groups, [4], [7].
Moreover, $0$–Hecke monoids have been applied in algebraic combinatorics, for
instance in [11]. Investigation of Hecke–Kiselman monoids and their algebras
fits into the study of various generalizations of algebraic structures arising
from Coxeter groups. Several combinatorial and structural properties of
Hecke–Kiselman monoids and their monoid algebras have already been studied for
example in [5, 6, 12, 13, 14].

The aim of the present paper is to describe the Gelfand–Kirillov dimension of
Hecke–Kiselman algebras associated to oriented graphs in terms of numerical
invariants of the underlying graph. This dimension describes an asymptotic
behaviour of the growth of algebras and is a useful tool in the study of
noncommutative algebras. For basic information on the Gelfand–Kirillov
dimension we refer to [8].

The following result obtained in [12] is our starting point.

######  Theorem 1.1.

Let $\Theta$ be a finite oriented simple graph. The following conditions are
equivalent.

  * (1)

$\Theta$ does not contain two different simple cycles connected by an oriented
path of length $\geq 0$,

  * (2)

$A_{\Theta}$ is an algebra satisfying a polynomial identity,

  * (3)

$\operatorname{GKdim}(A_{\Theta})<\infty$,

  * (4)

the monoid $\operatorname{HK}_{\Theta}$ does not contain a free submonoid of
rank $2$.

Our reasoning relies on the property discovered in [13], saying that the
Hecke–Kiselman algebras associated to oriented graphs are automaton algebras.
This class of algebras was introduced as a generalization of algebras with
finite Gröbner basis, [17]. An automaton algebra is an algebra whose set of
normal forms is recognised by a finite deterministic automaton. This property
implies several consequences for the combinatorics and growth of the algebra.
In particular, the Gelfand–Kirillov dimension of automaton algebras is an
integer if it is finite, [17], and can be expressed using certain forms of
elements of the algebra, [16]. To obtain our main result in Theorem 3.6 we
investigate the combinatorics of words in Hecke–Kiselman monoids. Gröbner
bases of Hecke–Kiselman algebras described in [13] and the characterization of
almost all elements of the monoid associated to an oriented cycle of any
length, obtained in [14], are extensively used in our approach.

##  2 Preliminaries

Following [17], let us recall some definitions that concern combinatorics on
words in the context of finitely generated algebras.

Let $F$ denote the free monoid on the set $X$ of $n\geq 3$ free generators
$x_{1},\dotsc,x_{n}$. Let $k$ be a field and let $k[F]=k\langle
x_{1},\dotsc,x_{n}\rangle$ denote the corresponding free algebra over $k$. For
every $x\in X$ and $w\in F$ by $|w|_{x}$ we mean the number of occurrences of
$x$ in $w$. By $|w|$ we denote the length of the word $w$. The support of
$w\in F$, denoted by $\operatorname{supp}(w)$, stands for the set of all $x\in
X$ such that $|w|_{x}>0$. We say that the word $w=x_{i_{1}}\cdots x_{i_{r}}\in
F$ is a subword of the word $v\in F$, where $x_{i_{j}}\in X$, if
$v=v_{1}x_{i_{1}}\cdots v_{r}x_{i_{r}}v_{r+1}$, for some
$v_{1},\ldots,v_{r+1}\in F$. If $v_{2},\ldots,v_{r}$ are trivial words, then
we say that $w$ is a factor of $v$. By a prefix (suffix) of the word $w$ we
mean any factor $u\neq 1$ such that $w=uv$ ($w=vu$) for some $v$.

Assume that a well order $<$ is fixed on $X$ and consider the induced degree-
lexicographical order on $F$ (also denoted by $<$). Let $A$ be a finitely
generated algebra over $k$ with a set of generators $r_{1},\ldots,r_{n}$ and
let $\pi:k[F]\to A$ be the natural homomorphism of $k$-algebras with
$\pi(x_{i})=r_{i}$. We will assume that $\ker(\pi)$ is spanned by elements of
the form $w-v$, where $w,v\in F$ (in other words, $A$ is a semigroup algebra).
Let $I$ be the ideal of $F$ consisting of all leading monomials of
$\ker(\pi)$. The set of normal words corresponding to the chosen presentation
for $A$ and to the chosen order on $F$ is defined by $N(A)=F\setminus I$.
Describing the set $N(A)$ is related to finding a Gröbner basis of the ideal
$J=\ker(\pi)$ of $k[F]$. Recall that a subset $G$ of $J$ is called a Gröbner
basis of $J$ (or of $A$) if $0\notin G$, $J$ is generated by $G$ as an ideal
and for every nonzero $f\in J$ there exists $g\in G$ such that the leading
monomial $\overline{g}\in F$ of $g$ is a factor of the leading monomial
$\overline{f}$ of $f$. If $G$ is a Gröbner basis of $A$, then a word $w\in F$
is normal if and only if $w$ has no factors that are leading monomials in
$g\in G$.

Gröbner bases of Hecke–Kiselman algebras associated to oriented graphs have
been characterized in [13]. For any oriented graph $\Theta$, $t\in V(\Theta)$
and $w\in F=\langle V(\Theta)\rangle$ we write $w\nrightarrow t$ if
$|w|_{t}=0$ and there are no $x\in\operatorname{supp}(w)$ such that
$x\rightarrow t$ in $\Theta$. Similarly, we define $t\nrightarrow w$: again we
assume that $|w|_{t}=0$ and there is no arrow $t\to y$, where
$y\in\operatorname{supp}(w)$. In the case when $t\nrightarrow w$ and
$w\nrightarrow t$, we write $t\nleftrightarrow w$. A vertex $v\in V(\Theta)$
is called a sink vertex if no arrow begins in $v$. Analogously one defines a
source vertex. Sink and source vertices are called terminal vertices.

######  Theorem 2.1 ([13]).

Let $\Theta$ be a finite simple oriented graph with vertices
$V(\Theta)=\\{x_{1},x_{2},\ldots,x_{n}\\}$. Extend the natural ordering
$x_{1}<x_{2}<\cdots<x_{n}$ on the set $V(\Theta)$ to the deg-lex order on the
free monoid $F=\langle V(\Theta)\rangle$. Consider the following set $T$ of
reductions on the algebra $k[F]$:

  * (i)

$(twt,tw)$, for any $t\in V(\Theta)$ and $w\in F$ such that $w\nrightarrow t$,

  * (ii)

$(twt,wt)$, for any $t\in V(\Theta)$ and $w\in F$ such that $t\nrightarrow w$,

  * (iii)

$(t_{1}wt_{2},t_{2}t_{1}w)$, for any $t_{1},t_{2}\in V(\Theta)$ and $w\in F$
such that $t_{1}>t_{2}$ and $t_{2}\nleftrightarrow t_{1}w$.

Then the set $\\{w-v,\text{ where }(w,v)\in T\\}$ forms a Gröbner basis of the
algebra $A_{\Theta}$.

To emphasize the use of the theorem above, whenever we consider the set
$N(A_{\Theta})$ of normal words of the Hecke–Kiselman algebra
$A_{\Theta}=k[\operatorname{HK}_{\Theta}]$ that is obtained via reductions
from the set $T$, we will say that the elements of $N(A_{\Theta})$ are the
reduced words of $A_{\Theta}$.

This result leads to the following corollary, obtained in [13], that will be
useful in calculation of the Gelfand–Kirillov dimension of Hecke–Kiselman
algebras.

######  Theorem 2.2.

Assume that $\Theta$ is a finite simple oriented graph. Then $A_{\Theta}$ is
an automaton algebra, with respect to any deg-lex order on the underlying free
monoid of rank $n$. Consequently, the Gelfand–Kirillov dimension
$\operatorname{GKdim}(A_{\Theta})$ of $A_{\Theta}$ is an integer if it is
finite.

Recall that $A$ is an automaton algebra if $N(A)$ is a regular language. That
means that this set is obtained from a finite subset of $F$ by applying a
finite sequence of operations of union, multiplication and operation $*$
defined by $T^{*}=\bigcup_{i\geq 0}T^{i}$, for $T\subseteq F$. Similarly, we
define $T^{+}=\bigcup_{i\geq 1}T^{i}$ for $T\subseteq F$. If $T=\\{w\\}$ for
some $w\in F$, then we write $T^{*}=w^{*}$ and $T^{+}=w^{+}$. An expression
built recursively from the set of letters from $F$ using operations of union,
multiplication and $*$ is called a regular expression. The importance of
automaton algebras comes from the deep results from the theory of automata.
Recall that a finite automaton is an oriented graph with two distinguished
sets of vertices (possibly intersecting), called initial and final states and
with edges labelled with letters of a finite alphabet $X$. An automaton is
called a deterministic automaton, if there is only one initial vertex and, at
every vertex, for every letter, there exists a unique edge beginning with that
vertex and marked by that letter. The language defined by an automaton
consists of the set of all the words formed by reading through a path from any
initial vertex to any final vertex. The famous Kleene’s theorem states that
every regular language may be defined by a deterministic automaton. This
property is especially useful in the case of automaton algebras of finite
Gelfand–Kirillov dimension, as we will see below.

It is known that the GK-dimension of an automaton algebra is either infinite
or an integer, see for example Theorem 3 on page 97 in [17]. Moreover, in the
finite dimensional case, the dimension is related to certain forms of regular-
expressions representations of the regular languages of normal words, [16]. We
reformulate the results of [16] to apply them in the case of Hecke–Kiselman
algebras.

Let us start with the necessary notations and remarks. The density function of
a regular language $L\subseteq F$, where $F$ is the free monoid over the set
$X$ is defined as $p_{L}(n)=|L\cap X^{n}|$, that is the number of elements in
$L$ of length $n$. Given two functions $f(n)$ and $g(n)$, we say that $f(n)$
is $O(g(n))$ if there are positive constants $C$ and $n_{0}$ such that
$f(n)\leqslant Cg(n)$ for every $n\geqslant n_{0}$. In particular, the density
function of the regular language $N(A)$ of normal words of an automaton
algebra $A$ is $O(n^{k-1})$ for some $k\geqslant 1$ precisely when the growth
of $A$ is $O(n^{k})$ and, consequently, $\operatorname{GKdim}(A)\leqslant k$.
Therefore the following can be obtained as a consequence of Theorem 3 in [16].

######  Theorem 2.3 ([16], Theorem 3).

The Gelfand–Kirillov dimension of an automaton algebra $A$ is not bigger than
$k$ for some $k\geqslant 0$ if and only if the set of normal words $N(A)$ can
be represented as a finite union of regular expressions of the following form

$v_{0}w_{i_{1}}^{*}v_{1}w_{i_{2}}^{*}v_{2}\ldots v_{s-1}w_{i_{s}}^{*}v_{s},$
(2.1)

with $v_{0},\ldots,v_{s}\in F$, $w_{i_{1}},\ldots,w_{i_{s}}\in F$ and
$0\leqslant s\leqslant k$.

We aim to determine the Gelfand–Kirillov dimension of the Hecke–Kiselman
algebra $A_{\Theta}$ in the finite-dimensional case. Due to Theorem 1.1, this
means that the graph $\Theta$ does not contain two cycles connected by an
oriented path. As we will show, in this case any family of words of form (2.1)
can be rewritten in such a way that each $w_{i_{j}}$ corresponds to a certain
cycle $C_{j}$ in the graph $\Theta$ and $v_{i}$ contains a vertex which is
connected by an edge with the cycle $C_{i+1}$ for $i\neq s$. To estimate the
dimension, we will find the maximal possible $s$ for the words of such form.

Every vertex of $\Theta$ that belongs to some cycle will be called a cycle
vertex, or a cycle generator of $\operatorname{HK}_{\Theta}$. Any vertex that
is not a cycle vertex will be called a non-cycle vertex (resp. a non-cycle
generator).

We end this section with a general observation concerning the possible forms
of elements $w_{i_{j}}$ in (2.1).

######  Observation 2.4.

Let $\Theta$ be a finite simple oriented graph such that $A_{\Theta}$ is of
finite Gelfand–Kirillov dimension. Let $C_{1},\ldots,C_{k}$ be the set of
disjoint simple cycles in $\Theta$, where $C_{l}$ is of the form

$x_{1,l}\to x_{2,l}\to\ldots\to x_{n_{l},l}\to x_{1,l},$

for some $n_{l}\geqslant 3$ and $1\leq l\leq k$. Assume any deg-lex order on
$F$ such that we have $x<y$ for some $x\in C_{r}$ and $y\in C_{s}$ if and only
if either $r<s$, or if $r=s$ and $x=x_{p,r},y=x_{q,r}$, for $p<q$. Assume that
for some $1\neq w\in F$, the words $w^{m}\in F$ are reduced with respect to
the reduction set $T$ in Theorem 2.1 (constructed with respect to the chosen
deg-lex order) for every $m\geqslant 1$. Then $w$ is a factor of the infinite
word of the form $(q_{N,i})^{\infty}$ of full support, where $x_{1}\to
x_{2}\to\ldots\to x_{N}\to x_{1}$ is one of the cycles $C_{k}$ with $N=n_{k}$,
$q_{N,i}=x_{N}(x_{1}\ldots x_{i})(x_{N-1}\ldots x_{i+1})$ and
$i\in\\{0,\ldots,N-2\\}$. Here we assume that $q_{N,0}=x_{N}x_{N-1}\ldots
x_{1}$.

###### Proof.

Let $w\neq 1$ be such that the word $w^{m}$ is reduced for every $m\geqslant
1$. Suppose that $y\in\operatorname{supp}(w)$ is a non-cycle vertex of
$\Theta$. First, we will show that then the support of $w$ would also contain
either a source or sink vertex. If $y$ is not a terminal vertex, from
conditions (i) and (ii) in Theorem 2.1, it follows that there exist
$u_{1},z_{1}\in V(\Theta)$, $u_{1}\neq z_{1}$, such that $u_{1}\rightarrow y$,
$z_{1}\leftarrow y$ in $\Theta$ and $u_{1},z_{1}\in\operatorname{supp}(w)$.
Similarly, if $u_{1}$ is not a sink vertex, then there exists
$u_{2}\in\operatorname{supp}(w)$ such that $u_{2}\rightarrow u_{1}$.
Symmetrically, if $z_{1}$ is not a source vertex, then $z_{2}\leftarrow z_{1}$
in $\Theta$ for some $z_{2}\in\operatorname{supp}(w)$. Moreover
$\\{u_{1},u_{2}\\}\cap\\{z_{1},z_{2}\\}=\emptyset$, because $y$ is a non-cycle
vertex and $z_{2}\notin\\{y,z_{1}\\}$, $u_{2}\notin\\{y,u_{1}\\}$. We continue
this procedure until at least one of the chosen vertices is either terminal or
cycle vertex. As the graph is finite, after finitely many steps we obtain a
path $u_{s}\rightarrow\cdots\rightarrow u_{1}\rightarrow y\rightarrow
z_{1}\rightarrow\cdots\rightarrow z_{r}$ such that
$u_{1},\ldots,u_{s},z_{1},\ldots,z_{r}\in\operatorname{supp}(w)$ and either
$u_{s}$ is a cycle vertex, or a source vertex and, similarly, either $z_{r}$
is a cycle vertex, or a sink vertex. From Theorem 1.1 and the assumption that
$A_{\Theta}$ is of finite Gelfand–Kirillov dimension, the graph $\Theta$ does
not contain two cycles connected by a path and thus it follows that $u_{s}$
and $z_{r}$ cannot be both cycle vertices. Therefore, either $u_{s}$ is a
source or $z_{r}$ is a sink, as claimed. However, according to Theorem 2.1 a
sink or source vertex may occur in a reduced word at most once. Since $w^{2}$
is reduced and contains at least two occurrences of $u_{s}$ and $z_{r}$, they
cannot be terminal vertices, which leads to a contradiction.

We have proved that the entire support of $w$ consists of cycle generators.
Call these cycles $C_{1},\ldots,C_{q}$. Since the Gelfand–Kirillov dimension
of $A_{\Theta}$ is finite, no vertex can belong to two cycles and if two
elements in the support of $w$ belong to different cycles, they are not
connected in $\Theta$ by an oriented path. From Theorem 2.1 and from the
assumed deg-lex order on $F$ it follows that $w=w_{1}w_{2}\ldots w_{q}$, where
$\operatorname{supp}(w_{p})\subseteq V(C_{i_{p}})$ for pairwise different
cycles $C_{i_{p}}$ for $p=1,\ldots,q$. Yet, as $w^{m}$ is reduced, for all
$m\geq 1$ it easily follows that $q=1$, so the support of $w$ belongs entirely
to a single cycle. Say that this cycle $C$ is of the form $x_{1}\to
x_{2}\to\ldots\to x_{N}\to x_{1}$. Suppose that there exists $x_{i}$ which is
not in the support of $w$. Take an index $i$ such that
$x_{i}\notin\operatorname{supp}(w)$ but $x_{i-1}\in\operatorname{supp}(w)$,
where for $i=1$ we take $i-1=N$. Then $w^{2}$ contains a factor of the form
$x_{i-1}ux_{i-1}$ such that $x_{i}\notin\operatorname{supp}(u)$. From the
description of the Gröbner basis in Theorem 2.1 it follows that then $w^{2}$
is not reduced. This means that
$\operatorname{supp}(w)=\\{x_{1},\ldots,x_{N}\\}$. From [14], Proposition 2.14
it follows that if $w^{n}$ is reduced for every $n\geqslant 1$, then for some
$m\geqslant 1$ the word $w^{m}$ is of the form $aq_{N,i}^{k}b$, where
$i\in\\{0,\ldots,N-2\\}$, $k\geqslant 1$ and $a$ and $b$ are members of an
explicitly described finite families of words. Then, from the assumption,
$w^{2m}$ has the reduced form $aq_{N,i}^{k}baq_{N,i}^{k}b$. In particular,
this word has a factor $q_{N,i}$ and therefore, from Theorem 2.1 in [14], it
follows that $ba$ is either of the form $q_{N,i}$ or the trivial word $1$.
Consequently, as $w$ is a prefix and suffix of $w^{m}=aq_{N,i}^{k}b$, it is
also a factor of the infinite word of the form $(q_{N,i})^{\infty}$ for some
$i\in\\{0,\ldots,N-2\\}$. The assertion holds. ∎

##  3 The main result

Consider an oriented graph $\Theta$ which does not contain two different
cycles connected by an oriented path. Then, by Theorem 1.1, the corresponding
Hecke–Kiselman algebra $A_{\Theta}=k[\operatorname{HK}_{\Theta}]$ is of finite
Gelfand–Kirillov dimension.

If the graph does not contain any oriented cycle, then the corresponding
Hecke–Kiselman monoid is finite, see for example [2]. In this case the
Gelfand–Kirillov dimension of the monoid algebra $A_{\Theta}$ is $0$.

Thus in the present section we assume that $\Theta$ has at least one cycle.
Denote the simple cycles of the graph by $C_{1},\ldots,C_{k}$ for some
$k\geqslant 1$ and assume that the cycle $C_{j}$ is of the length
$i_{j}\geqslant 3$ for $j=1,\ldots,k$.

Let $\Theta^{\prime}$ be the full subgraph of $\Theta$ whose set of vertices
is built from all cycle vertices and all vertices connected with at least one
cycle by an oriented path. We will call such a subgraph $\Theta^{\prime}$ the
maximal cycle–reachable subgraph of $\Theta$.

In particular, for any vertex $x\in V(\Theta^{\prime})$ that is not contained
in any cycle, if there exists a path from $x$ to a cycle (from a cycle to $x$,
respectively), then all paths between $x$ and all cycles are from $x$ to the
cycles (from the cycles to $x$, respectively), as otherwise $\Theta$ would
contain two different cycles connected by an oriented path.

Consider any degree-lexicographic order in the free monoid generated by the
vertices of $\Theta$. Recall that by reduced words we mean the words that are
in the normal form with respect to the set of reductions from Theorem 2.1.

We start with the estimation of the number of occurrences of certain non-
cyclic vertices in the reduced words of Hecke–Kiselman monoids. We agree that
for any vertex $x$ there exists exactly one path of length $0$ with the end
(or beginning) in $x$.

######  Lemma 3.1.

Let $\Theta$ be a finite simple oriented graph with cycles denoted by
$C_{1},\ldots,C_{k}$, and let $\Theta^{\prime}$ be its maximal cycle-reachable
subgraph. For every vertex $x\in
V(\Theta^{\prime})\setminus(V(C_{1})\cup\ldots\cup V(C_{k}))$ either all
oriented paths between $x$ and any cycle lead from $x$ into cycles or all lead
from cycles into $x$. Denote by $k_{x}$ the number of oriented paths in
$\Theta$ of non-negative length with the end in the vertex $x$ in the first
case, and the number of oriented paths of non-negative length with the
beginning in $x$ in the latter case. Then, in every reduced word in
$\operatorname{HK}_{\Theta}$, the element $x$ occurs at most $k_{x}$ times.

###### Proof.

Let $x$ be any vertex contained in the maximal cycle–reachable subgraph
$\Theta^{\prime}$ of the graph $\Theta$ but not contained in the cycles
$C_{1},\ldots,C_{k}$. Assume first that there are oriented paths from the
cycles into $x$. To prove the statement we proceed by induction on the maximal
length $l(x)$ of a path starting at $x$ in the graph $\Theta$.

If $l(x)=0$ then $x$ is a sink vertex in the graph $\Theta$ and thus there are
no edges starting at $x$. Then for any $w\in\operatorname{HK}_{\Theta}$ we
have $xwx=wx$ (see condition (ii) in Theorem 2.1) and thus $x$ can occur at
most once in any reduced word.

Assume now that $l(x)>0$ for some $x\in
V(\Theta^{\prime})\setminus(V(C_{1})\cup\ldots\cup V(C_{k}))$ and let
$z_{1},\ldots,z_{m}$ be the set of all vertices in $\Theta$ such that there is
an edge $x\rightarrow z_{i}$ for every $i=1,\ldots,m$. Then from the
definition of the maximal cycle–reachable subgraph it follows that all
$z_{1},\ldots,z_{m}$ are also in $\Theta^{\prime}$. Moreover, for
$i=1,\ldots,m$ we have $l(z_{i})<l(x)$. By the inductive hypothesis every
$z_{i}$ occurs in any reduced word at most $k_{z_{i}}$ times, where
$k_{z_{i}}$ is number of paths starting at $z_{i}$. We know that if a word of
the form $xwx$ with $|w|_{x}=0$ is reduced in $\operatorname{HK}_{\Theta}$
then in particular $x\rightarrow y$ for some $y\in\operatorname{supp}(w)$, as
otherwise $x\nrightarrow w$ and $xwx=wx$ in $\operatorname{HK}_{\Theta}$. It
follows that at least one of $z_{1},\ldots,z_{m}$ occurs between any two
generators $x$. As already explained, every $z_{i}$ occurs in any reduced word
at most $k_{z_{i}}$ times. Therefore $x$ can occur at most
$k_{z_{1}}+\ldots+k_{z_{m}}+1$ times in any reduced word. On the other hand,
in $\Theta$ there is exactly one path of length $0$ starting at $x$. Every
other path starting from $x$ uniquely determines a path starting from one of
$z_{1},\ldots,z_{m}$ and every path $p$ starting at $z_{i}$ defines a path
starting with $x\rightarrow z_{i}$ and followed by $p$. Thus, in total there
are exactly $k_{z_{1}}+\ldots+k_{z_{m}}+1$ paths starting from $x$ in the
graph $\Theta$. The assertion follows.

The case where there exist paths from $x$ to a cycle can be treated by a
symmetric argument, using induction on the maximal length of a path that ends
in $x$.

∎

Note that for every non-cyclic vertex $x$ in the maximal cycle–reachable
subgraph $\Theta^{\prime}$ such that all paths between $x$ and the cycles lead
from the cycles into $x$ (from $x$ into the cycles, respectively) the number
$k_{x}$ of all paths in $\Theta$ starting (ending, respectively) at $x$ is the
same as the number of such paths in $\Theta^{\prime}$.

Our next step is to use Lemma 3.1 to show that every regular expression of the
form $w_{1}^{*}v_{1}w_{2}^{*}\ldots v_{s-1}w_{s}^{*}$ which describes reduced
words in the algebra $A_{\Theta}$ can be expressed using at most certain
number of stars. To do so we need to introduce certain order in the set of
vertices of $\Theta$. For the rest of the present section we will assume that
such an order had been chosen.

######  Definition 3.2 (Order on vertices of the graph).

Let $\Theta$ be a graph with the cycles $C_{1},\ldots C_{k}$ of length
$n(j)\geqslant 3$ for $j=1,\ldots,k$. Denote by $\Theta^{\prime}$ the maximal
cycle–reachable subgraph of $\Theta$. As already explained, for any vertex $x$
of $\Theta^{\prime}$ that is not contained in any cycle, all oriented paths
between $x$ and any of the cycles starts either from $x$ or all go to $x$. For
every such a vertex denote by $k_{x}$ the number of oriented paths of length
$\geqslant 0$ in $\Theta$ with either the end or the beginning in $x$,
depending on the direction of paths between $x$ and the cycles. In the set of
these vertices define any order such that if $k_{x}<k_{y}$ holds, then $y<x$.

Let $C_{j}$ be of the form $x_{1,j}\rightarrow\cdots\rightarrow
x_{n(j),j}\rightarrow x_{1,j}$ for some $n(j)\geqslant 3$ and $j=1,\ldots,k$.
In the set of all cycle vertices introduce the order such that
$x_{i,j}<x_{l,m}$ if ether $j<m$ or $j=m$ and $i<l$. Moreover, assume that all
cycle vertices are smaller than any vertex outside the cycles.

Finally, choose any order in the set of vertices of $\Theta$ that are not in
$\Theta^{\prime}$, for example such that all these vertices are bigger than
the vertices of $\Theta^{\prime}$.

Let us note that it is possible to define the order which satisfies all above
conditions provided that the graph $\Theta$ does not contain two different
cycles connected by an oriented path.

In the next lemma we describe the possible form of a family of reduced words
described by $w^{*}vw^{*}$, with $\operatorname{supp}(w)\subseteq V(C_{n})$
for some $n$.

######  Lemma 3.3.

If a family of reduced words is described by a regular expression of the form
$u^{*}vw^{*}$ with $\operatorname{supp}(u),\operatorname{supp}(w)\subseteq
V(C_{n})$ for a cycle $C_{n}$, then either $v$ contains a vertex connected by
an edge with $C_{n}$ or this family of words can be expressed by a sum of
finitely many regular expressions of the form $pr^{*}q$ or $p$, for some words
$p,q$ and $r$.

###### Proof.

Let $u^{*}vw^{*}$ be the regular expression describing reduced words with
$\operatorname{supp}(u),\operatorname{supp}(w)\subseteq V(C_{n})$ for a cycle
$C_{n}$. First we claim that either $\operatorname{supp}(v)\subseteq V(C_{n})$
or $v$ contains a non-cycle vertex. Indeed, by Definition 3.2 of the order on
the vertices of $\Theta$ and the fact that the graph does not contain two
different cycles connected by an oriented path, generators corresponding to
the vertices from different cycles commute. Consequently, every reduced word
$w$ such that $\operatorname{supp}(w)\subseteq V(C_{1})\cup\cdots\cup
V(C_{k})$ has elements from different cycles grouped in such a way that if
$w=w_{1}\cdots w_{j}$ with $w_{i}\in V(C_{n(i)})$ and $w_{l}\in V(C_{n(l)})$,
then $n(i)\leqslant n(l)$ for all $i<l$. Thus if the family of words
$u^{*}vw^{*}$ such that
$\operatorname{supp}(u),\operatorname{supp}(w)\subseteq V(C_{n})$ is reduced,
then either $\operatorname{supp}(v)\subseteq V(C_{n})$ or $v$ contains a non-
cycle generator.

Let us now consider the first case, that is $u^{*}vw^{*}$ consists of reduced
words and $\operatorname{supp}(u)$, $\operatorname{supp}(v)$,
$\operatorname{supp}(w)\subseteq V(C_{n})$. We proceed to show that then
$u^{*}vw^{*}$ can be expressed as a finite sum of expressions with at most one
Kleene star. From the reasoning as in the proof of Observation 2.4 it follows
that $u,v$ and $w$ are all factors of the infinite word $(x_{N}(x_{1}\ldots
x_{l})(x_{N-1}\ldots x_{l+1}))^{\infty}$, denoted shortly by
$q_{N,l}^{\infty}$, for some $l\in\\{0,\ldots,N-2\\}$, where $N$ depends on
$n$. Moreover we can write $u=aq_{N,l}^{\alpha_{1}}b$,
$v=aq_{N,l}^{\beta}b^{\prime}$ and
$u=a^{\prime}q_{N,l}^{\alpha_{2}}b^{\prime}$ for non-negative $\alpha_{i}$,
$\beta$ and words $a,a^{\prime}$, $b,b^{\prime}$ that are suffixes and
prefixes of the word $q_{N,l}$, respectively, of length at most $N-1$. Thus
both $ba$ and $b^{\prime}a^{\prime}$ are either the trivial word $1$ or are of
the form $q_{N,l}$. Then $u^{*}vw^{*}$ is equal to the set
$\\{aq_{N,l}^{l_{1}\beta_{1}+l_{2}\beta_{2}+\beta_{3}}b^{\prime}:l_{1},l_{2}\geqslant
0\\}$, for some positive integers $\beta_{i}$ ($i=1,2,3$), where
$\beta_{1}=\alpha_{1}$ if $ba=1$ and $\beta_{1}=\alpha_{1}+1$ otherwise, and
$\beta_{2}=\alpha_{2}$ if $b^{\prime}a^{\prime}=1$ and
$\beta_{2}=\alpha_{2}+1$ otherwise. From Proposition 2.2 in [15] it follows
that there exist a positive integer $n_{0}$ and a finite set $F$ such that
$\\{l_{1}\beta_{1}+l_{2}\beta_{2}+\beta_{3}\\}=\\{n_{0}+kd:k\geqslant 0\\}\cup
F$, where $d=\operatorname{gcd}{(\beta_{1},\beta_{2})}$. We thus get easily
that $u^{*}vw^{*}$ can be written as a finite sum of regular expressions with
at most one star $*$.

Now assume that a family of reduced words described by $u^{*}vw^{*}$ is such
that $\operatorname{supp}(u),\operatorname{supp}(w)\subseteq V(C_{n})$ and $v$
contains a non-cycle vertex. We can write $v=v_{s}zv_{c}$ for words
$v_{s},v_{c}$ and a non-cycle vertex $z$ such that
$\operatorname{supp}(v_{c})\subseteq\bigcup\limits_{j=1}^{k}V(C_{j})$. Suppose
that $z$ is not connected by an edge with a cycle $C_{n}$. Consider the first
occurrence of a vertex $x$ such that $x\in V(C_{n})$ in the word $v_{c}w$.
Then the word $vw$ contains a factor of the form $zv^{\prime}x$ with
$\operatorname{supp}(v_{c})\subseteq\bigcup\limits_{j\neq n}V(C_{j})$.
Furthermore, $x<z$ and $zv^{\prime}\nleftrightarrow x$. Consequently, $vw$
contains a factor which can be reduced using reduction (iii) from Theorem 2.1.
The obtained contradiction shows that for every family of reduced words of the
form $u^{*}vw^{*}$ with
$\operatorname{supp}(u),\operatorname{supp}(w)\subseteq V(C_{n})$ and
$\operatorname{supp}(v)\nsubseteq V(C_{n})$, for a cycle $C_{n}$, factor $v$
contains at least one vertex connected by an edge with $C_{n}$. Thus, the
result follows. ∎

######  Corollary 3.4.

If $\Theta$ is an oriented graph with the cycles $C_{1},\ldots,C_{k}$ such
that the corresponding Hecke–Kiselman algebra has finite Gelfand–Kirillov
dimension then

$\operatorname{GKdim}A_{\Theta}\leqslant\sum_{j=1}^{k}\left(\sum_{x\in\mathcal{A}_{j}}k_{x}+1\right),$

where $\mathcal{A}_{j}$ consists of all vertices of $\Theta$ that are
connected by an edge with the cycle $C_{j}$ for $j=1,\ldots,k$.

###### Proof.

It is enough to prove that every family of reduced words in $A_{\Theta}$ of
the form

$w_{1}^{*}v_{1}w_{2}^{*}\ldots v_{s-1}w_{s}^{*}$

can be expressed as a regular expression of the form (2.1) with
$s\leqslant\sum_{j=1}^{k}\sum_{x\in\mathcal{A}_{j}}\left(k_{x}+1\right)$.

From Observation 2.4 for every $n$ we have
$\operatorname{supp}(w_{n})\subseteq V(C_{j(n)})$, for some
$j(n)\in\\{1,\ldots,k\\}$ and $w_{n}$ are factors of the word
$(x_{N}(x_{1}\ldots x_{i})(x_{N-1}\ldots x_{i+1}))^{\infty}$ of full support,
where $x_{1}\to x_{2}\to\ldots\to x_{N}\to x_{1}$ is one the cycles $C_{j}$
with $N=n(j)$ and $i\in\\{0,\ldots,N-2\\}$.

By Lemma 3.3 we can rewrite the considered family of words in such a way that
between any two $w_{i}$, $w_{j}$ ($i,j\in\\{1,\ldots,s\\}$) such that
$\operatorname{supp}(w_{i}),\operatorname{supp}(w_{j})\subseteq V(C_{n})$ for
some $n\in\\{1,\ldots,k\\}$ there is a non-cycle vertex $z$ which is connected
by an edge with $C_{n}$, that is $z\in\mathcal{A}_{n}$.

By Lemma 3.1, all vertices $z$ with this property occur at most
$\sum_{x\in\mathcal{A}_{n}}k_{x}$ times in total in any reduced word of
$A_{\Theta}$. Consequently, in the regular expression of the above form, for
every $j=1,\ldots,k$, factors of the form $w^{*}$ with
$\operatorname{supp}(w)\subseteq V(C_{j})$ occur at most
$\sum_{x\in\mathcal{A}_{j}}k_{x}+1$ times.

Because, as already explained, any family of reduced words in $A_{\Theta}$ of
the form $w_{1}^{*}v_{1}w_{2}^{*}\ldots v_{s-1}w_{s}^{*}$ can be rewritten in
such a way that for every $w_{i}$ we have $\operatorname{supp}(w_{i})\subseteq
V(C_{j})$ for some $j\in\\{1,\ldots,k\\}$, it follows that
$s\leqslant\sum_{j=1}^{k}\left(\sum_{x\in\mathcal{A}_{j}}k_{x}+1\right)$.

From Theorem 2.3 we know that the set of normal (reduced) words of
$A_{\Theta}$ is a finite union of regular expressions of the form
$v_{0}w_{i_{1}}^{*}v_{1}w_{i_{2}}^{*}v_{2}\ldots v_{s-1}w_{i_{s}}^{*}v_{s}$.
Therefore, from the above reasoning and Theorem 2.3 it follows that
$\operatorname{GKdim}A_{\Theta}\leqslant\sum_{j=1}^{k}\left(\sum_{x\in\mathcal{A}_{j}}k_{x}+1\right)$,
as claimed. ∎

Our next step is to construct a family of reduced words of the algebra
$A_{\Theta}$ described by a regular expression with exactly
$s=\sum_{j=1}^{k}\left(\sum_{x\in\mathcal{A}_{j}}k_{x}+1\right)$ stars and
such that for different substitutions of stars with positive integers we get
different elements. As for every word $w$ we have $w^{*}w=w^{+}$, we will
write $w^{+}$ instead of $w^{*}w$ and we refer to the number of stars in the
regular expression even if $+$ is used.

Let us recall that we assume that the set of vertices of $\Theta$ is ordered
as in Definition 3.2.

Let $\Theta$ be a graph with cycles $C_{1},\ldots,C_{k}$ of the length
$i_{j}\geqslant 3$ for $j\in\\{1,\ldots,k\\}$. Denote by $\Theta^{\prime}$ the
maximal cycle–reachable subgraph of $\Theta$. We will construct a family of
reduced words in $\operatorname{HK}_{\Theta}$ via an insertion process that is
described below.

Step 1. First we insert subsequent vertices contained in the cycle–reachable
subgraph $\Theta^{\prime}$ of the graph $\Theta$ that are not cycle vertices
to certain words, starting from the trivial word $1$. At every step a chosen
generator $y$ is inserted at the beginning of the word and directly after
every vertex of the (previously constructed) word that is connected by an edge
with $y$. Every vertex $y$ occurs exactly $k_{y}$ times in the constructed
word. Note that at this stage the resulting word is not necessarily reduced.
The procedure is described precisely as follows.

As $\Theta$ does not contain two different cycles connected by an oriented
path, either there is at least one terminal vertex $y$ with $k_{y}=1$ or the
graph is a disjoint union of cycles $C_{1},\ldots,C_{k}$. If the latter case
holds we set $w^{\prime}=1$, where $1$ is a trivial word and go to Step 2.

Now we consider the case when there are some terminal vertices in
$\Theta^{\prime}$. Note that a vertex $y$ from $\Theta^{\prime}$ is terminal
exactly if $k_{y}=1$. Let $y^{(1)}_{1}<\ldots<y^{(1)}_{n_{1}}$ be the set of
all vertices in $\Theta^{\prime}$ such that $k_{y^{(1)}_{i}}=1$ and define

$w_{1}=y^{(1)}_{1}y^{(1)}_{2}\cdots y^{(1)}_{n_{1}}.$

Next, take the biggest (with respect to the order defined in Definition 3.2)
vertex $y^{(2)}\in V(\Theta^{\prime})$ that is not contained in any cycle of
the graph and that has not been used yet in $w_{1}$. We can assume that all
paths between the cycles and $y^{(2)}$ lead from the cycles into $y^{(2)}$.
Otherwise, all such paths lead from $y^{(2)}$ into the cycles and the
reasoning is symmetric. If for some non-cycle vertex $z\in V(\Theta^{\prime})$
we have $y^{(2)}\rightarrow z$, then $k_{z}<k_{y^{(2)}}$ and thus $y^{(2)}<z$.
By the choice of $y^{(2)}$ it follows that
$z\in\\{y^{(1)}_{1},\ldots,y^{(1)}_{n_{1}}\\}$. Moreover, there are exactly
$k_{y^{(2)}}-1$ (recall that $k_{y^{(2)}}$ is the number of paths starting at
$z$) generators in $w_{1}$ that are connected by an edge with $y^{(2)}$. Let
$w_{2}$ be the word that is formed from $w_{1}$ by inserting the generator
$y^{(2)}$ in such a way that it is the first letter of $w_{2}$ and $y^{(2)}$
also directly follows in $w_{2}$ every $y^{(1)}_{j}$ that is connected by an
edge $y^{(2)}\rightarrow y^{(1)}_{j}$ with $y^{(2)}$ in $\Theta^{\prime}$.
Generator $y^{(2)}$ occurs in $w_{2}$ exactly $k_{y^{(2)}}$ times.
Additionally, every generator $z$ used in the word $w_{2}$ occurs in this word
exactly $k_{z}$ times.

Similarly, if we have already constructed the word $w_{i}$ for some $i>1$,
then in the next step we insert to this word several copies of the largest
non-cycle generator $y^{(i+1)}\in V(\Theta^{\prime})$ that is not in the
support of $w_{i}$ yet. In the word $w_{i}$ every generator $z$ occurs $k_{z}$
times. We know that every $z$ such that $y^{(i+1)}<z$ is already in the
support of $w_{i}$. In particular every generator $z$ for which
$k_{z}<k_{y^{(i+1)}}$ is in $w_{i}$. As explained above, we can assume that
all directed paths connecting the cycles and $y^{(i+1)}$ start from the
cycles. Therefore, if we have $y^{(i+1)}\rightarrow p$ in the graph
$\Theta^{\prime}$, then $p\in\operatorname{supp}(w_{i})$. Define the word
$w_{i+1}$ by inserting $y^{(i+1)}$ to $w_{i}$ at the beginning and also
directly after every generator $z\in\operatorname{supp}(w_{i})$ such that
$y^{(i+1)}\rightarrow z$ in $\Theta^{\prime}$. In such a word $w_{i+1}$ the
element $y^{(i+1)}$ occurs exactly $\sum\limits_{y^{(i+1)}\rightarrow
z}k_{z}+1$ times. Let us note that all paths starting at $y^{(i+1)}$ in the
graph $\Theta$ are either the path of length $0$ or are uniquely determined by
a path starting at $z$ for some $z$ such that $y^{(i+1)}\rightarrow z$.
Consequently, in the word $w_{i+1}$ the element $y^{(i+1)}$ occurs exactly
$\sum\limits_{y^{(i+1)}\rightarrow z}k_{z}+1=k_{y^{(i+1)}}$ times.

After finitely many steps as described above we get a word $w^{\prime}$ whose
support contains every non-cycle generator $z$ of $\Theta^{\prime}$ and with
the property that every $z\in\operatorname{supp}(w^{\prime})$ occurs in
$w^{\prime}$ exactly $k_{z}$ times.

Step 2. Now we insert cycle vertices into the word $w^{\prime}$ constructed in
Step 1. The idea relies on a slight modification of the previous Step. Namely,
we insert regular expressions of the form $w_{0}w^{*}w_{1}$ with
$\operatorname{supp}(w_{0}),\operatorname{supp}(w_{1}),\operatorname{supp}(w)\subseteq
V(C_{j})$ ($w_{0}$ and $w_{1}$ vary depending on the insertion place), for a
cycle $C_{j}$, at the beginning of the constructed regular expression and
directly after every vertex connected by an edge with $C_{j}$. The procedure
is repeated for every cycle, starting from the cycle with the biggest vertices
in the sense of ordering from Definition 3.2. It can be precisely described as
follows.

For every cycle $C_{i}$ ($i=1,\ldots,k$) with vertices
$x_{1,i},\ldots,x_{n,i}$ for some $n\geqslant 3$ denote by $c_{i}$ the reduced
word of the form $x_{1,i}\cdots x_{n,i}$.

We can write $w^{\prime}=v_{1}\cdots v_{m+1}$, where every $v_{i}$ is the word
of minimal possible length that ends with an element $z_{i}$ connected by an
edge with the cycle $C_{k}$ (possibly with $v_{m+1}=1$) for $i=1,\ldots,m$.
Note that we have $m=\sum_{x\in\mathcal{A}_{k}}k_{x}$ if $\mathcal{A}_{k}$ is
non-empty and $m=0$ otherwise.

For every vertex $z_{i}$ connected by an edge with the cycle $C_{k}$ of length
$n$, we may choose $j(i)\in\\{1,\ldots,n\\}$ such that either
$z_{i}\rightarrow x_{j(i),k}$ or $x_{j(i),k}\rightarrow z_{i}$. Then we define
the regular expression (that is certain family of words) $r_{k}$ as follows:

$\displaystyle c_{k}^{+}(x_{1,k}\ldots x_{j(1)-1,k})v_{1}(x_{j(1),k}\cdots
x_{n,k})c_{k}^{+}(x_{1,k}\ldots x_{j(2)-1,k})\cdots$ $\displaystyle\cdots
c_{k}^{+}(x_{1,k}\ldots x_{j(m)-1,k})v_{m}(x_{j(m),k}\cdots
x_{n,k})c_{k}^{+}v_{m+1}.$

In this expression Kleene star $*$ occurs exactly
$m_{k}=\sum_{x\in\mathcal{A}_{k}}k_{x}+1$ times, where $\mathcal{A}_{k}$
consists of all vertices $x$ that are connected by an edge with the cycle
$C_{k}$ in $\Theta^{\prime}$. If $\mathcal{A}_{k}$ is empty, that is there are
no vertices connected by an edge with the cycle $C_{k}$ and $w^{\prime}=v_{1}$
we define the regular expression $r_{1}$ as $c_{k}^{+}v_{1}$. Then we also
assume that $\sum_{x\in\mathcal{A}_{k}}k_{x}=0$ and thus Kleene star $*$
occurs exactly $1=\sum_{x\in\mathcal{A}_{k}}k_{x}+1$ times.

Next we repeat this procedure for every cycle of the graph $\Theta$. More
precisely, at every step we rewrite the constructed regular expression $r_{j}$
as $v_{1}\cdots v_{m+1}$, where $v_{1},\ldots,v_{m}$ are regular expressions
of minimal possible length that end with an element $z_{i}$ connected by an
edge with the cycle $C_{j-1}$ (perhaps with $v_{m+1}=1$). If there are no
vertices connected by an edge with $C_{j-1}$, we set $r_{j}=v_{1}$, that is
$m=0$. Note that we have $m=\sum_{x\in\mathcal{A}_{j-1}}k_{x}$, where for
empty $\mathcal{A}_{j-1}$ we put $\sum_{x\in\mathcal{A}_{j-1}}k_{x}=0$. For
every vertex $z_{i}$ connected by an edge with the cycle $C_{j-1}$ of length
$n$, we may choose $j(i)\in\\{1,\ldots,n\\}$ such that either
$z_{i}\rightarrow x_{j(i),j-1}$ or $x_{j(i),j-1}\rightarrow z_{i}$. Then
define the regular expression $r_{j-1}$ as:

$\displaystyle c_{j-1}^{+}(x_{1,j-1}\ldots
x_{j(1)-1,j-1})v_{1}(x_{j(1),j-1}\cdots x_{n,j-1})c_{j-1}^{+}(x_{1,j-1}\ldots
x_{j(2)-1,j-1})\cdots$ (3.1) $\displaystyle\cdots c_{j-1}^{+}(x_{1,j-1}\ldots
x_{j(m)-1,j-1})v_{m}(x_{j(m),j-1}\cdots x_{n,j})c_{j-1}^{+}v_{m+1}.$

As before, if $\mathcal{A}_{j-1}$ is empty, we set $r_{j-1}=c_{j-1}^{+}r_{j}$.
Then expression $r_{j-1}$ contains exactly
$m_{j-1}=m_{j}+\sum_{x\in\mathcal{A}_{j-1}}k_{x}+1$ Kleene stars.

This way we construct a regular expression $r_{1}$ that contains exactly
$m_{1}=m_{2}+\sum_{x\in\mathcal{A}_{1}}k_{x}+1=\sum_{j=1}^{k}\left(\sum_{x\in\mathcal{A}_{j}}k_{x}+1\right)$
stars. We will show that $r_{1}$, treated as a family of words, consists of
reduced words of $\operatorname{HK}_{\Theta}$. This will be crucial to get the
lower bound for the Gelfand–Kirillov dimension of the algebra $A_{\Theta}$.

######  Lemma 3.5.

Words (3.1) are reduced in $A_{\Theta}$ with respect to the system introduced
in Theorem 2.1. Consequently,
$\operatorname{GKdim}A_{\Theta}\geqslant\sum_{j=1}^{k}\left(\sum_{x\in\mathcal{A}_{j}}k_{x}+1\right)$.

###### Proof.

We will show that no leading term of reductions of the form (i)–(iii) listed
in Theorem 2.1 appears as a factor of a word $w$ from the family described by
the regular expression $r_{1}$.

Reductions of type (i) and (ii). First consider any factor of $w$ of the form
$tvt$ for some generator $t$ and any word $v$ such that
$t\notin\operatorname{supp}(v)$. We need to show that then there are vertices
$x,y\in\operatorname{supp}(v)$ such that $x\rightarrow v$ and $v\rightarrow
y$.

Assume first that $t$ is a cycle vertex, let $t\in V(C_{j})$ for a cycle
$C_{j}$ with vertices $x_{1,j},\ldots,x_{n,j}$ and some
$j\in\\{1,\ldots,k\\}$. Consider the image of elements of the family described
by a regular expression (3.1) under the natural projection
$\varphi_{j}:\operatorname{HK}_{\Theta}\rightarrow\operatorname{HK}_{C_{j}}$
onto the Hecke–Kiselman monoid associated to the cycle $C_{j}$, such that
$\varphi_{j}(x)=1$ for all $x\notin V(C_{j})$.

By the construction, every such image is a factor of $(x_{1,j}\cdots
x_{n,j})^{\infty}$. Thus if $t$ is a cycle vertex $x_{i}$, then
$x_{i-1},x_{i+1}\in\operatorname{supp}(v)$, where for $i=1$ and $i=n$ we set
$i-1=n$ and $i+1=1$, respectively. In particular it is then impossible to have
$t\nrightarrow v$ or $t\nleftarrow v$. Therefore, we may consider any $t$ that
is not in the cycle and we claim that in every factor $tvt$ the set
$\operatorname{supp}(v)$ contains elements $p$ and $q$ connected by an edge
with $t$ such that $t\rightarrow p$ and $q\rightarrow t$.

Note that every sink or source vertex $x$ either is not contained in the
maximal cycle–reachable subgraph $\Theta^{\prime}$ of the graph or $k_{x}=1$.
Consequently, it occurs at most once in every word described by the considered
regular expression. Thus we know that $t$ is neither a sink nor a source
vertex.

Now assume that $t$ is non-cycle and not terminal vertex, see Section 2, from
$\Theta^{\prime}$. Assume first that all oriented paths connecting $t$ with
the cycles lead from the cycles to $t$. For any $z\rightarrow t$ contained in
the graph $\Theta^{\prime}$ we have $z<t$. From the construction of the family
of words it follows that such $z$ is inserted into the word between any two
occurrences of $t$, that is $z\in\operatorname{supp}(v)$ and the leading term
from the reduction (i) in Theorem 2.1 is impossible. The other way round, the
generator $t$ is inserted into the regular expression at the beginning and
directly after any vertex $y$ such that $t\rightarrow y$ ($y$ are inserted
before $t$). In particular, all such generators $y$ occur between any two
$t$’s. It follows directly that no leading term of a reduction of type (ii)
appears as a factor of $w$. The case when all oriented paths lead from $t$ to
the cycles can be handled in much the same way.

Reductions of type (iii). We claim that $w$ does not contain any factor
$t_{1}vt_{2}$ such that $t_{1}>t_{2}$ and $t_{2}\nleftrightarrow t_{1}v$. If
$t_{1}$ is contained in any of the cycles, then $t_{1}>t_{2}$ implies that
also $t_{2}$ is a cycle vertex.

Let a word $w$ be described by a regular expression (3.1). By the
construction, for every factor of $w$ of the form $px_{i,j}$, where $x_{i,j}$
is a cycle vertex and $p$ is a word such that $p\nleftrightarrow x_{i,j}$, the
word $p$ consists of cycle vertices $x_{l,m}$ such that $m<j$. In particular
we have $g<x_{i,j}$ for every $g\in\operatorname{supp}(p)$. Thus there is no
factor of the above form with $t_{2}$ being a cycle element.

In consequence, we can assume that both $t_{1}$ and $t_{2}$ are non-cycle
vertices.

We claim that no word $w_{i}$ from the first part of the construction of
regular expression $r_{1}$ has a factor of type (iii) from Theorem 2.1. To do
so, we proceed by induction on $i$. First observe that the assertion holds for
$i=1$, as generators in $w_{1}$ are in the increasing order. Hence, assume
that the claim holds for some $w_{i}$ and denote by $y^{(i+1)}$ the vertex
inserted in the next step, that is
$\operatorname{supp}(w_{i+1})\setminus\operatorname{supp}(w_{i})=\\{y^{(i+1)}\\}$.
Then every factor $t_{1}vt_{2}$ such that $t_{1}>t_{2}$ and
$t_{2}\nleftrightarrow t_{1}v$ in $w_{i+1}$ would have $t_{2}=y^{(i+1)}$
because by the inductive hypothesis $w_{i}$ does not have such factors and all
elements of $\operatorname{supp}(w_{i})$ are bigger than $y^{(i+1)}$. On the
other hand, in $w_{i+1}$ the element directly before $y^{(i+1)}$ is connected
by an edge with $y^{(i+1)}$. Thus in $w_{i+1}$ every factor of the form
$t_{1}vy^{(i+1)}$ with $t_{1}>y^{(i+1)}$ is such that the last generator of
$t_{1}v$ is connected by an edge with $y^{(i+1)}$. The inductive assertion
holds.

Consequently, we know that the word $w^{\prime}$, built in the first step of
the construction, does not contain factors of type (iii). The regular
expression $r_{1}$ is obtained from $w^{\prime}$ by inserting only cycle
generators. Every factor $t_{2}vt_{1}$ with $t_{2}>t_{1}$ and
$t_{2}\nleftrightarrow t_{1}w$ would therefore start or end with a cycle
vertex, that is either $t_{1}$ or $t_{2}$ is a cycle vertex. This is not
possible as we explained earlier. We have proved that any $w$ described by the
regular expression $r_{1}$ does not contain factors of the form (iii) in the
Theorem 2.1, as claimed. The first part of lemma follows.

As every word described by the regular expression $r_{1}$ is reduced, two
different words are equal in the algebra $A_{\Theta}$ if and only if they are
equal as elements of free monoid generated by the vertices of $\Theta$.

Let us notice that every element $w$ of this family of words is uniquely
determined by $m$ positive integers $(n_{1},\ldots,n_{m})$, where
$m=\sum_{j=1}^{k}\left(\sum_{x\in\mathcal{A}_{j}}k_{x}+1\right)$, such that
$n_{1},\ldots,n_{m}$ are powers of consecutive cycles of the form
$(x_{1,j}\cdots x_{n,j})$ that correspond exactly to stars $*$. If a family is
of the form $v_{0}w_{i_{1}}^{*}v_{1}w_{i_{2}}^{*}v_{2}\ldots
v_{m-1}w_{i_{m}}^{*}v_{m}$, denote by $q$ the length of the word
$v_{0}v_{1}\ldots v_{m-1}v_{m}$ and let $K$ be the maximal length of cyclic
subgraph in $\Theta$. Then the number of elements of length at most $n$ in
this family, denoted by $d(n)$ for $n\geqslant 1$, is not smaller than the
number of elements of the set
$\\{(n_{1},\ldots,n_{m}):n_{i}\in\mathbb{Z}_{+},n_{1}+\cdots+n_{m}\leqslant\frac{n-q}{K}\\}$.
It follows that for almost all $n$ we have $d(n)\geqslant d_{m}(Cn)$ for
certain constant $C$, where $d_{m}$ is the growth function of polynomials in
$m$ variables. Consequently, from Example 1.6 in [8], it follows that
$\operatorname{GKdim}A_{\Theta}\geqslant\sum_{j=1}^{k}\left(\sum_{x\in\mathcal{A}_{j}}k_{x}+1\right)$.
∎

Corollary 3.4 and Lemma 3.5 are summarized in the following theorem that
describes the Gelfand–Kirillov dimension of the Hecke–Kiselman algebra
associated to any oriented graph without two different cycles connected by an
oriented path.

######  Theorem 3.6.

Let $\Theta$ be a finite simple oriented graph with the cycles
$C_{1},\ldots,C_{k}$ for some $k\geqslant 1$ without two different cycles
connected by an oriented path. In particular, for any non-cyclic vertex $x$
connected by an oriented path with a cycle either all paths between $x$ and
cycles are directed from $x$ into the cycles or all begin at the cycles.
Denote by $\mathcal{A}_{j}$ the set of vertices of the graph that are
connected by an edge with the cycle $C_{j}$ for $j=1,\ldots,k$. For any
$x\in\mathcal{A}_{j}$ let $k_{x}$ be the number of oriented paths of length
$\geqslant 0$ in $\Theta$ that start with $x$ if all paths between $C_{j}$ and
$x$ start with the cycle vertices and oriented paths that end with $x$
otherwise. Then

$\operatorname{GKdim}A_{\Theta}=\sum_{j=1}^{k}\left(\sum_{x\in\mathcal{A}_{j}}k_{x}+1\right),$

where $\sum_{x\in\mathcal{A}_{j}}k_{x}+1$ is equal to $1$ if $\mathcal{A}_{j}$
is an empty set. Lastly, if the graph $\Theta$ does not contain any cycle,
then $\operatorname{GKdim}A_{\Theta}=0$.

##  4 An example

Let us illustrate concepts from Theorem 3.6 and its proof for the oriented
graph $\Theta$ presented in the picture.

${\Theta}$${y_{2}}$${y_{3}}$${y_{6}}$${y_{1}}$${y_{5}}$${{x_{3,1}}}$${y_{4}}$${{x_{3,2}}}$${{x_{1,1}}}$${{x_{2,1}}}$${{x_{1,2}}}$${{x_{2,2}}}$

The maximal cycle–reachable subgraph $\Theta^{\prime}$ is the full subgraph of
$\Theta$ with all vertices except $y_{6}$. The edges of $\Theta^{\prime}$ are
denoted by solid arrows, whereas the complement is denoted by dashed ones.

For the non-cycle vertices in $\Theta^{\prime}$ named as in the picture we
have: $k_{y_{2}}=k_{y_{3}}=k_{y_{4}}=k_{y_{5}}=1$ and $k_{y_{1}}=3$. Denote
the cycle with vertices $x_{i,1}$, $i=1,2,3$ by $C_{1}$ and let $C_{2}$ be the
cycle $x_{1,2}\rightarrow x_{2,2}\rightarrow x_{3,2}\rightarrow x_{1,2}$. Then
the sets $\mathcal{A}_{1}$ and $\mathcal{A}_{2}$ consisting of the vertices
connected by an edge with the cycles are $\mathcal{A}_{1}=\\{y_{1},y_{4}\\}$
and $\mathcal{A}_{2}=\\{y_{4},y_{5}\\}$. We get that
$\sum_{x\in\mathcal{A}_{1}}k_{x}+1=5$ and
$\sum_{x\in\mathcal{A}_{2}}k_{x}+1=3$.

From Theorem 3.6 we obtain the following corollary.

######  Corollary 4.1.

The Gelfand–Kirillov dimension of the Hecke–Kiselman algebra $A_{\Theta}$
associated to the graph $\Theta$ as in the picture is $8$.

Following Lemma 3.5 let us construct a family of reduced words in $A_{\Theta}$
described by a regular expression with exactly $8$ Kleene stars.

In the set of vertices of $\Theta$ we introduce the following order.

  * •

Cycle vertices are such that
$x_{1,1}<x_{2,1}<x_{3,1}<x_{1,2}<x_{2,2}<x_{3,2}$.

  * •

For non-cyclic vertices we may choose any order such that $y_{1}$ is the
smallest one. Assume that $y_{1}<y_{2}<y_{3}<y_{4}<y_{5}<y_{6}$.

  * •

All cycle vertices are smaller than non-cyclic ones, that is $x_{3,2}<y_{1}$.

Then the word $w^{\prime}$ without cycle vertices built in the first part of
the construction is of the form $y_{1}y_{2}y_{1}y_{3}y_{1}y_{4}y_{5}$. Note
that each element $y_{j}$ of the support of this word occurs in it exactly
$m_{y_{j}}$ times. Next denote by $c_{i}$ the word $x_{1,i}x_{2,i}x_{3,i}$ for
$i=1,2$. We have that every vertex of $c_{1}$ is smaller than any vertex of
$c_{2}$. The regular expression $r_{2}$ is
$c_{2}^{+}y_{1}y_{2}y_{1}y_{3}y_{1}y_{4}c_{2}^{+}x_{1,2}x_{2,2}y_{5}x_{3,2}c_{2}^{+}$.
Finally, the regular expression $r_{1}$ with exactly $8$ stars and consisting
of reduced words has the following form:

$(c_{1}^{+}x_{1,1}x_{2,1})(c_{2}^{+})\underline{y_{1}}(x_{3,1}c_{1}^{+}x_{1,1}x_{2,1})\underline{y_{2}y_{1}}(x_{3,1}c_{1}^{+}x_{1,1}x_{2,1})\underline{y_{3}y_{1}}(x_{3,1}c_{1}^{+}x_{1,1})\underline{y_{4}}(x_{2,1}x_{3,1}c_{1}^{+})(c_{2}^{+}x_{1,2}x_{2,2})\underline{y_{5}}(x_{3,2}c_{2}^{+}).$

The consecutive factors of $w^{\prime}$ constructed in the first step are
underlined for clarity.

Acknowledgments. I am very grateful to Jan Okniński for careful reading and
many suggestions on the earlier versions of the paper, as well as his
continuous support. I would also like to thank Arkadiusz Mecel for fruitful
discussions about the research topic.

This work is supported by grant 2021/41/N/ST1/03082 of the National Science
Centre (Poland).

## References

  * [1] D.N. Ashikhmin, M.V. Volkov, W.T. Zhang,The finite basis problem for Kiselman monoids, Demonstratio Mathematica 48 (2015), 475–492.
  * [2] R. Aragona, A. D’Andrea, Hecke–Kiselman monoids of small cardinality, Semigroup Forum 86 (1) (2013), 32–40.
  * [3] G.M. Bergman, The diamond lemma for ring theory, Advances in Mathematics 29 (1978), 178–218.
  * [4] T. Denton, F. Hivert, A. Schilling, N.M. Thiery, On the representation theory of finite J–trivial monoids, Seminaire Lotharingien de Combinatoire 64 (2011), Art. B64d.
  * [5] L. Forsberg, Effective representations of Hecke–Kiselman monoids of type A. https://arxiv.org/abs/1205.0676 (2014).
  * [6] O. Ganyushkin, V. Mazorchuk, On Kiselman quotients of $0$-Hecke Monoids, Int. Electron. J. Algebra 10(2) (2011), 174–191.
  * [7] J. Huang, A tableau approach to the representation theory of 0-Hecke algebras, Annals of Combinatorics 20(4) (2016), 831–868.
  * [8] G.R. Krause, T.H. Lenagan, Growth of Algebras and Gelfand-Kirillov Dimension, Pitman, London, 1985.
  * [9] G. Kudryavtseva, V. Mazorchuk, On Kiselman’s semigroup, Yokohama Math. J., 55(1) (2009), 21–46.
  * [10] J. Krempa, J. Okniński, Gefand-Kirillov dimensions of a tensor product, Math Z. 194 (1987), 487–494.
  * [11] E. Marberg, On some actions of the 0-Hecke monoids of affine symmetric groups, Journal of Combinatorial Theory. Series A, 161 (2019), 178–219.
  * [12] A. Mecel, J. Okniński, Growth alternative for Hecke-Kiselman monoids, Publicacions Mathemàtiques, 63 (2019), 219–240.
  * [13] A. Mecel, J. Okniński, Gröbner basis and the automaton property of Hecke–Kiselman algebras, Semigroup Forum 99 (2019), 447–464.
  * [14] J. Okniński, M. Wiertel, Combinatorics and structure of Hecke–Kiselman algebras, Communications in Contemporary Mathematics, 22 (07) (2020), 2050022 (42 pages).
  * [15] J.C. Rosales, P. A. García-Sánchez, Numerical Semigroups, Developments in Mathematics, vol.20, Springer, 2009.
  * [16] A. Szilard, S. Yu, K. Zhang, J. Shallit, Characterizing regular languages with polynomial densities, Proceedings of the 17th International Symposium on Mathematical Foundations of Computer Science, Lecture Notes in Computer Science 629, Springer-Verlag, Berlin (1992) 494-503.
  * [17] V.A. Ufnarovskii, Combinatorial and Asymptotic Methods in Algebra, in: Encyclopedia of Mathematical Sciences vol. 57, pp.1–196, Springer, 1995.

Magdalena Wiertel
email address<EMAIL_ADDRESS>
Institute of Mathematics
University of Warsaw
Banacha 2
02-097 Warsaw, Poland