\mychapter{Generalizing the $\mathcal{P}$-graph}

\section{A general construction}

The aim of this section is to extend the (generalized) $\mathcal{P}$-graph
construction, described below, to subdirect products of monoids. We reformalize our definition of
$\mathcal{P}$-graph as follows.

\vspace{.2in} \noindent\textbf{Definition}. A pair
$\mathbf{G}=(G,\mathcal{P})$ is a \emph{partition}-\emph{graph}
(or a $\mathcal{P}$-\emph{graph} for short) if $G=(V,E)$ is a graph and
$\mathcal{P}=\{V_i\mid i\in I\}$ is a partition of $V$ into
independent sets and there exists $0\in I$ (we shall distinguish
the set $V_0$ by the term ``axis") such that for any $i\in
I\setminus\{0\}$ the graph induced on $V_0\cup V_i$ is a star
forest saturating $V_i$. More explicitly the following holds:
\begin{enumerate}
\item [(d1)] for every $i\in I\setminus \{0\}$ and for every $x\in
V_i$ there exists $ y\in V_0$ with $\{x,y\}\in E$; \item [(d2)]
for every $i\in I$ and every $y\in V_0$ there exists at most one
$x\in V_i$ with $\{x,y\}\in E$.
\end{enumerate}
\vspace{.1in}

We call $|I|$ the \emph{width} of $\mathbf{G}$, and denote it by
$w(\mathbf{G})$.
\vspace{.2in}

\noindent\textbf{Definition}. We say that a $\mathcal{P}$-graph
$\mathbf{G}$ \emph{represents a monoid} $M=(M,\cdot ,e)$ if the
axis $V_0$ can be identified with $M$ such that:
\begin{enumerate}
\item [(r1)] the restriction of every
$f\in\End_{\mathcal{P}}(\mathbf{G})$ to $M$ is a left translation
of $M$; \item [(r2)] for every left translation $\lambda$ of $M$
there exists $f\in\End_{\mathcal{P}}(\mathbf{G})$ with
$f(x)=\lambda(x)$ for all $ x\in M$; \item [(r3)] for distinct
$f,f'\in\End_{\mathcal{P}}(\mathbf{G})$ there exists $x\in M$ with
$f(x)\neq f'(x)$.
\end{enumerate}
\vspace{.1 in}

It is easy to see that $\mathcal{P}$-graphs constructed in
Proposition 3.4 represent monoids in the sense of our definition.

Observe that if $\mathbf{G}$ represents a monoid $M$ (we assume
that $M=V_0$) then the restriction of a given
$f\in\End_{\mathcal{P}}(\mathbf{G})$ to $M$ is a left translation
by $f(e)$ and hence, if $f$ and $f'$ are distinct
$\mathcal{P}$-endomorphisms, then $f(e)\neq f'(e)$.

For a monoid $M$ let $\Pi(M)$ denote the least natural number $n$
such that there exists a $\mathcal{P}$-graph $G$ representing $M$
with $|V(G)|\leq n$ and $\End(G)\cong M$. For a class
$\mathcal{M}$ of monoids set
$$\Pi_{\mathcal{M}}(m)=\max\{\Pi(M)\mid M\in\mathcal{M},|M|=
m\}.$$ As before, we can restrict ourselves to an investigation of
$\mathcal{P}$-endomorphism monoids. Using our enhanced notation, we can restate
Proposition 3.1 as follows.

\paragraph{Theorem 5.1.} Let $\mathbf{G}$ be a $\mathcal{P}$-graph.
Then there exists a graph $H$ with $\End_{\mathcal{P}}(\mathbf
{G})\cong\End(H)$ and $|H|=|G|+4w(\mathbf{G})+5$.

The above construction for the graph $H$ yields the best known
upper bound for the general case. For products, however, instead
of applying the construction directly we will get an improved
bound by ``piecing together" the $\mathcal{P}$-graphs corresponding
to the factors in an efficient way. Let $M^{(1)},M^{(2)},\ldots ,
M^{(r)}$ be monoids. The elements of a product monoid
$\prod_{i=1}^{r}M^{(i)}$ are $r$-tuples $(m^{(1)},m^{(2)},\ldots ,
m^{(r)})$ with multiplication defined coordinatewise. A submonoid
$M\subset \prod_{i=1}^{r}M^{(i)}$ is called a \emph{subdirect}
\emph{product} if the projection $\pi^{(i)}:M\rightarrow M^{(i)}$
is surjective for all $i$.

Recall that a family $\{f^{(i)}:X\rightarrow X^{(i)}\mid i\in
I\}$ of mappings is \emph{separating} if for every pair $\{x,y\}$
of distinct elements of $X$ there exists $i\in I$ with
$f^{(i)}(x)\neq f^{(i)}(y)$. Observe that the set of projections
$\{\pi^{(i)}\mid 1\leq i\leq r\}$ is separating.

We can now give our construction of a (generalized) $\mathcal{P}$-graph with
given endomorphism monoid.

\paragraph{Construction 5.2.}Let us assume that
\begin{enumerate}
\item[(a)] $\mathfrak
{G}=\{\mathbf{G}^{(i)}=(G^{(i)},\mathcal{P}^{(i)})\mid i\in I\}$
is a family of disjoint $\mathcal{P}$-graphs where for each $i\in
I$
\begin{itemize}
\item $G^{(i)}=(V^{(i)},E^{(i)})$, \item
$\mathcal{P}^{(i)}=\{V^{(i)}_j\mid j\in J^{(i)}\}$, \item
$0^{(i)}\in J^{(i)}$ is the axis of $\mathbf{G}^{(i)}$;
\end{itemize}
\item[(b)] $V_0$ is a set such that for every $i\in I$
\begin{itemize}
\item $0\notin J^{(i)}$, \item $|V_0|\geq |V_{0^{(i)}}^{(i)}|$,
\item $V_0\cap V^{(i)}=\emptyset$;
\end{itemize}
\item [(c)] $\mathfrak{F}=\{f^{(i)}:V_0\rightarrow
V_{0^{(i)}}^{(i)}\mid i\in I\}$ is a family of surjective
mappings.
\end{enumerate}
Define a $\mathcal{P}$-graph
$\mathbf{G}(\mathfrak{G},\mathfrak{F},V_0)=\mathbf{G}
=((V,E),\mathcal{P})$ where
\begin{itemize}
\item $V=V_0\cup (\bigcup_{i\in I}V^{(i)})$, \item
$\mathcal{P}=\{V_0\}\cup\{V_j^{(i)}\mid i\in I,\,j\in J^{(i)}\}$,
\item $V_0$ is the axis of $\mathbf{G}$, \item $E=(\bigcup_{i\in
I}E^{(i)})\cup \{\{v,f^{(i)}(v)\}\mid v\in V_0,i\in I\}\cup
(\bigcup_{i\in I}F^{(i)})$
\end{itemize}
where $F^{(i)}\subseteq V_0\times V^{(i)}$ consists of all pairs
$\{u,v\}$ where $u\in V_0$ such that
$$\{u,v\}\in F^{(i)}\quad\text{just when}\quad \{f^{(i)}(u),v\}\in E^{(i)}.$$

We observe that
\begin{equation}
|\mathbf{G}|=|V_0|+\sum_{i\in
I}|\mathbf{G}^{(i)}|\quad\textrm{and}\quad w(\mathbf{G}
)=1+\sum_{i\in I}w(\mathbf{G}^{(i)}).\end{equation} \vspace{.1 in}

Theorem 5.3 describes the $\mathcal{P}$-endomorphism monoid
of $\mathbf{G}(\mathfrak{G},\mathfrak{F},V_0)$.

\paragraph{Theorem 5.3.} Let $\mathfrak{F}=\{f^{(i)}:M\rightarrow M^{(i)}\mid i
\in I\}$ be a separating family of surjective monoid homomorphisms
and $\mathfrak{G}=\{\mathbf{G}^{(i)}\mid i\in I\}$ be a family of
$\mathcal{P}$-graphs such that $\mathbf{G}^{(i)}$ represents
$M^{(i)}$ for all $i\in I$. Then $\mathbf{G}(\mathfrak
{G},\mathfrak{F},M)$ represents $M$, consequently $\Pi(M) \leq |M|
+\sum_{i\in I}\Pi(M^{(i)})$.


\paragraph{Proof:}Given family $\mathfrak{G}$ and $\mathfrak{F}$ set $V_0=M$ and let
$\mathbf{G}=\mathbf{G}(\mathfrak{G},\mathfrak{F},V_0)$ be as in
Construction 5.2. Since $\mathbf{G}^{(i)}$ represents
$M^{(i)}$ we conclude that $V_{0^{(i)}}^{(i)}=M^{(i)}$.

We prove that $\mathbf{G}$ represents $M$ by verifying the three
conditions (r1),(r2) and (r3). To prove (r1) consider a
$\mathcal{P}$-endomorphism $f$ of $\mathbf{G}$. Then necessarily
$f(M)\subseteq M$. First we prove that \begin{equation}
f^{(i)}(f(m))=f(f^{(i)}(m))~\textrm{for all}~m\in
M~\textrm{and}~i\in I.\end{equation} By definition,
$\{m,f^{(i)}(m)\}\in E$ for all $m\in M$ and $i\in I$. Since $f$
is a $\mathcal{P}$-endomorphism we obtain
$\{f(m),f(f^{(i)}(m))\}\in E$ and $f(f^{(i)}(m))\in
M^{(i)}=V_{0^{(i)}}^{(i)}$ because $f^{(i)}(m)\in M^{(i)}$. Since,
by (d2), there exists at most one $v\in M^{(i)}$ with
$\{f(m),v\}\in E$ and, by construction,  $v=f^{(i)}(f(m))$ we
conclude that $f(f^{(i)}(m))=f^{(i)}(f(m))$ and (2) is proved.

Then for every $i\in I$ the restriction of $f$ to $V^{(i)}$ is a
$\mathcal {P}$-endomorphism of $\mathbf{G}^{(i)}$ and since
$\mathbf{G}^{(i)}$ represents $M^{(i)}$ we obtain, by (r1) applied
to $\mathbf{G}^{(i)}$, that the restriction of $f$ to $ M^{(i)}$
is $\lambda^{(i)}_{f(e^{(i)})}$. By (2),
$f(e^{(i)})=f(f^{(i)}(e))=f^{(i)}(f(e))$. Hence, for every $v\in M$
and every $i\in I$ we have
$$f^{(i)}(f(v))=f(f^{(i)}(v))=\lambda^{(i)}_{f^{(i)}(f(e))}(f^{(i)}(v))=
f^{(i)}(f(e))f^{(i)}(v)=f^{(i)}(f(e)v).$$ Since $\{f^{(i)}\mid
i\in I\}$ is a separating family of mappings we conclude that
$f(v)=f(e)v=\lambda_{f(e)}(v)$ for all $v\in M$ and (r1) is
proved.

To prove (r2) consider a left translation $\lambda_x$ of $M$.
Since $\mathbf{G}^{(i)}$ represents $M^{(i)}$ we may apply (r2) to
$\lambda^{(i)}_{f^{(i)}(x)}$ to obtain a
$\mathcal{P}$-endomorphism $g^{(i)}$ of $\mathbf{G}^{(i)}$ such
that the restriction of $g^{(i)}$ to $M^{(i)}$ is
$\lambda^{(i)}_{f^{(i)}(x)}$. Define $g:V\rightarrow V$ setting
for $v\in V$
$$g(v) =\left\{\begin{array}{ll} \lambda_x(v)&\text{ if }v\in M\\
g^{(i)}(v)&\text{ if }v\in V^{(i)}\text{ for some }i\in I.
\end{array}\right.$$
We are going to verify that $g$ is a $\mathcal{P}$-endomorphism of
$\mathbf{G}$. Since $g^{(i)}$ is a $\mathcal{P}$-endomorphism of
$\mathbf{G}^{(i)}$ for all $i\in I$ and since $M$ is an independent
set in $G$ it suffices to show that $\{g(u),g(v)\}\in E(G)$
whenever $\{u,v\}\in E(G)$ for $u\in M$ and $v\in V^{(i)}$ for
some $i\in I$. If $u\in M$ and $v\in V^{(i)}$ for some $i\in I$
then $\{u,v\}\in E(G)$ if and only if either $v=f^{(i)}(u)$ or
$\{f^{(i)}(u),v\}\in E(G^{(i)})$. Since
$$g(f^{(i)}(u))=g^{(i)}(f^{(i)}(u))=\lambda^{(i)}_{f^{(i)}(x)}(f^{(i)}(u))=
f^{(i)}(x)f^{(i)}(u)=f^{(i)}(xu)$$ and $xu=\lambda_x(u)=g(u)$ we
infer that $g(f^{(i)}(u))=f^{(i)}(g(u))$. Thus if $v=f^{(i)}(u)$
then $\{g(u),g(v)\}=\{g(u),f^{(i)}(g(u))\}\in E(G)$. Assume now
that $\{f^{(i)}(u),v\}\in E(G^{(i)})$. Combining
$f^{(i)}(g(u))=g(f^{(i)}(u))=g^{(i)}(f^{(i)}(u))$ and $g^{(i)}$ is
a $\mathcal{P}$-endomorphism of $\mathbf{G}^{(i)}$ we infer that
$\{f^{(i)}(g(u)),g(v)\}=\{f^{(i)}(g(u)),g^{(i)}(v)\}\in
E(G^{(i)})$. Consequently, $\{g(u),g(v)\}\in E(G)$ and (r2) is
proved.

To prove (r3) consider two $\mathcal{P}$-endomorphisms $f$ and $g$
of $\mathbf{G}$. We prove that if $f(m)=g(m)$ for all $m\in M$
then $f=g$. Choose $i\in I$. By (2),
$f(e^{(i)})=f(f^{(i)}(e))=f^{(i)}(f(e))$ and
$g(e^{(i)})=g(f^{(i)}(e))=f^{(i)}(g(e))$ for all $i\in I$. Hence
if $f(e)=g(e)$ then $f(e^{(i)})=g(e^{(i)})$ and applying (r1) to
$\mathbf{G}^{(i)}$ we infer that $f(x)=g(x)$ for all $x\in
M^{(i)}$. By (r3) applied to $\mathbf{G}^{(i)}$, we infer that
$f(v)=g(v)$ for all $v\in V_i$. Since $i\in I$ was arbitrary we
conclude that $f=g$ and (r3) is proved. Whence
$\mathbf{G}(\mathfrak{G}, \mathfrak{F},M)$ represents $M$ as
desired.$\Box$


To apply Theorem 5.3 we require a technical folklore lemma
about separating families.

\paragraph{Lemma 5.4.}Let $X$ be a set of size $n>1$. If
$\{f^{(i)}:X\rightarrow X^{(i)}\mid i\in I\}$ is a separating
family of mappings then there exists $I'\subseteq I$ such that
$|I'|\leq n-1$ and $\{f^{(i)}:X\rightarrow X^{(i)}\mid i\in I'\}$
is a separating family.


\paragraph{Proof:}We prove the statement by induction over $n$. If $n=2$
then the statement is trivial, it suffices to set $I'=\{i\}$ for
$i\in I$ such that $f_i$ is not constant. Assume that $|X|=n$ and
that the statement is true for all sets $Y$ with $|Y|<n$. Since
$\{f^{(i)}:X\rightarrow X^{(i)}\mid i\in I\}$ is separating there
exists $i_0\in I$ such that $f^{(i_0)}$ is non-constant.
Consequently, there exists a partition $\{Y_1,Y_2\}$ of $X$ such
that $f^{(i_0)}(y_1)\neq f^{(i_0)}(y_2)$ for all $y_1\in Y_1$ and
$ y_2\in Y_2$. Let $g^{(i)}$ be the restriction of $f^{(i)}$ to
$Y_1$ and $h^{(i)}$ be the restriction of $f^{(i)}$ to $Y_2$. Then
$\{g^{(i)}:Y_1\rightarrow X^{(i)}\mid i\in I\}$ and
$\{h^{(i)}:Y_2\rightarrow X^{(i)}\mid i\in I\}$ are separating
families because $\{f^{(i)}:X\rightarrow X^{(i)}\mid i\in I\}$ is
a separating family. By the induction hypothesis, there exist
$I_1,I_2\subseteq I$ such that $|I_1|\leq |Y_1|-1$, $|I_2|\leq
|Y_2|-1$, $\{g^{(i)}:Y_1\rightarrow X^{(i)}\mid i\in I_1\}$ and
$\{h^{(i)}: Y_2\rightarrow X^{(i)}\mid i\in I_2\}$ are separating
families because $|Y_1|,|Y_2|<n$. Then $\{f^{(i)}:X\rightarrow
X^{(i)}\mid i\in \{i_0\}\cup I_1\cup I_2\}$ is a separating family
and $|\{i_0\}\cup I_1\cup I_2|\leq 1+|I_1|+|I_2|\leq
1+|Y_1|-1+|Y_2|-1= |X|-1$.
$\Box$

\vspace{.1 in}

Next we give a consequence for classes of monoids which are
subdirect products of finitely many monoids. Let $\mathcal{M}$ be
a class of monoids for which there exist natural numbers $a$ and
$b$ such that $\Pi(M)\leq a$ for all $M\in\mathcal{M}$ and
$$b=\max_{M\in \mathcal{M}}\min\{w(\mathbf{G})\mid\mathbf{G} ~\textrm{represents}~
M~\textrm{and}~|\mathbf{G}|\leq a\}.$$

\paragraph{Corollary 5.5.}Let $M=(M_,\cdot ,e)$ be a monoid
for which there exists a separating family $\{f^{(j)}:M\rightarrow
M^{(j)}\mid j\in J\}$ of surjective monoid homomorphisms such that
$M^{(j)}\in \mathcal{M}$ for all $j\in J$. Then there exists a
$\mathcal{P}$-graph $\mathbf{G}$ representing $M$ such that
$|\mathbf{G}|\leq (a+1)|M|$ and $w (\mathbf{G})=b|M|$.


\paragraph{Proof:}By Lemma 5.4, we can assume that $|J|\leq |M|-1$.  We
apply Construction 5.2 and Theorem 5.3 which ensures
the existence of a $\mathcal{P}$-graph $\mathbf{G}$ representing
$M$ such that
$$|\mathbf{G}|\leq |M|+(|M|-1)a\leq (a+1)|M|,\quad w(\mathbf{G})\leq 1+(
|M|-1)b\leq |M|b.$$
$\Box$




\section{Application}

The aim of this section is to prove Theorem 7.

\vspace{.2in} \noindent\textbf{Definition}. A \emph{semilattice
monoid} is a commutative monoid $M$ satisfying $x^2=x$ for all
$x\in M$.

\paragraph{Proposition 5.6.}Let $S=(S,\cdot ,e)$ be a
semilattice monoid. Then there exists a $\mathcal{P}$-graph
$\mathbf{G}$ representing $S$ such that $|\mathbf{G}|\leq 4|S|$
and $w(\mathbf{G})\leq 2|S|$. Thus, $\Pi_{\mathcal{L}}(n)\leq 4n$.


\paragraph{Proof:}Let $\mathcal{M}$ be the single element class consisting of a
two-element semilattice. It is well-known that every semilattice
monoid is a subdirect product of two-element semilattices [P] and thus
Corollary 5.5 applies. Clearly, there exists a
$\mathcal{P}$-graph $\mathbf{G}$ (an edge and an isolated vertex)
representing a two-element semilattice with $|\mathbf{G}|=3$ and
$w (\mathbf{G})=2$. The statement then follows from Corollary 5.5.
$\Box$

Below we will use the following notation. For a semigroup
$S=(S,\cdot)$ we write $S^1=(S\cup \{1\},\cdot )$ or $S^0=(S\cup
\{0\},\cdot )$ where $1$ or $0$ is a new element which is not in
$S$ and $1s=s1=s$ for all $s\in S\cup \{1\}$ and $0s=s0=0$ for all
$s\in S\cup \{0\}$. Then $S^1$ is a monoid with an outer identity
and $S^0$ is a semigroup with an outer zero.

Next we prove an auxiliary technical lemma that plays a key role
in the next section. By the above definition, if $M=(M,\cdot ,e)$
is a monoid then $M^0$ is a monoid $M$ with adjoined outer zero.

\paragraph{Lemma 5.7.}Let $\mathbf{G}$ be a $\mathcal{P}$-graph
representing a monoid $M$, then there exists a $\mathcal{P}$-graph
$\mathbf{H}$ representing $M^0$ such that
$$|\mathbf{H}|=|\mathbf{G}|+w(\mathbf{G})+3\quad\text{and }\quad w(\mathbf{H})
=w(\mathbf{G})+2.$$


\paragraph{Proof:}Let us assume that $\mathbf{G}=(G=(U,F),\mathcal{P})$ where
$\mathcal{P}=\{U_i\mid 0\leq i\leq l-1\}$ and $U_0$ is the axis of
$\mathbf{G}$. Let $M=(M,\cdot ,e)$ be a monoid. Assume that $
0\notin M$ and $M^0=(M\cup \{0\},\cdot ,e)$. Below we will relabel
$0$ by $v_0$ and suppose that $v_0$, $v_1$,\dots,$v_{l+1}$, and
$w$ are pairwise distinct and
$U\cap\{v_0,v_1,\dots,v_{l+1},w\}=\emptyset$. For $i$ with $0\leq
i\leq l-1$ set $V_i=U_i\cup\{v_i\}$, $V_l=\{w,v_l\}$,
$V_{l+1}=\{v_{l+1}\}$, and $V=\bigcup_{i=0}^{l+1}V_i$. Finally set
$E=F\cup E_1\cup E_2$ where $E_1=\{\{v_i,v_j\}\mid 0\leq i<j\leq
l+1\}$ and $E_2=\{\{u,w\}\mid u\in U\}$. Let
$\mathbf{H}=(H=(V,E),\mathcal{R})$ where $\mathcal{R}=\{V_i\mid
0\leq i\leq l+1\}$ and the axis is $V_0$. Clearly, $\mathbf{H}$ is
a $\mathcal{P}$-graph with
$|\mathbf{H}|=|\mathbf{G}|+w(\mathbf{G})+3$ and
$w(\mathbf{H})=w(\mathbf{G})+2$. It remains to prove that
$\mathbf{H}$ represents $M^0$ - the details of (r1),(r2)
and (r3) are below.

\paragraph{Details of 5.7}
Since $\mathbf{G}$ represents $M$ we have $U_0=M$ and thus,
(recalling that $0$ and $v_0$ are identified)
$V_0=M\cup\{0\}=M^0$. To prove (r1) for $\mathbf{H}$ and $M^0$
consider a $\mathcal{P}$-endomorphism $f$ of $\mathbf{H}$. First
observe that $\{v_i\mid 0\leq i\leq l+1\}$ induces a unique clique
of size $l+2$ in $\mathbf{H}$ and hence $f(\{v_i\mid 0\leq i\leq
l+1\})=\{v_i\mid 0\leq i\leq l+1\}$. For $j=0,1,\dots,l+1$ we have
$V_j\cap\{v_i\mid 0\leq i\leq l+1\}=\{v_j\}$ and consequently
$f(v_j)=v_j$ for all $j=0,1,\dots, l+1$, in particular, $f(0)=0$.
First assume that $f(e)\in M\subseteq V_0$. Observe that for $v\in
V$ we have $\{v,w\}\in E$ if and only if $v\in U$. Since
$V_l=\{w,v_l\}$ we conclude that $f(w)=w$ and $f(U)\subseteq U$.
Thus the restriction $g$ of $f$ to $U$ is a
$\mathcal{P}$-endomorphism of $\mathbf{G}$. Applying (r1) to
$\mathbf{G}$ and $M$ we conclude that $g(x)=\lambda^M_{f(e)}(x)$
for all $x\in M$ and hence $f(x)=\lambda^{M^0}_{f(e)}(x)$ for all
$x\in M^0$. On the other hand, if $f(e)=0$ then $f(w)=v_l$ because
$\{e,w\},\{0,v_l\}\in E$ and $\{0,w\}\notin E$. Since $\{u,w\}\in
E$ for all $u\in U$ and since $\{x,v_l\}\in E$ exactly when
$x\in\{v_i\mid 0\leq i\leq l+1,\,i\ne l\}$ we infer that
$f(V_i)=\{v_i\}$ for all $i\in\{0,1,\dots,l+1\}$. Thus
$f(x)=\lambda^{M^0}_0(x)$ for all $x\in M^0$ and (r1) is proved
for $\mathbf{H}$ and $M^0$.

To prove (r2) consider a left translation
$\lambda_a^{M^0}:M^0\rightarrow M^0$. First assume that $a\in M$.
 Applying (r2) to $\mathbf{G}$ and $M$ there exists a
$\mathcal{P}$-endomorphism $g$ of $\mathbf{G}$ such that
$g(x)=\lambda^M_a(x)$ for all $x\in M$. Define a mapping
$f:V\rightarrow V$ by
$$
f(v)=\left\{%
\begin{array}{ll}
   g(v)&\text{ if }v\in U \\
    v&\text{ if }v\in\{v_i\mid 0\leq i\leq l+1\}\cup\{w\}. \\
\end{array}%
\right.$$ Since $g$ is a $\mathcal{P}$-endomorphism of
$\mathbf{G}$ we obtain that $f$ is a $\mathcal{P}$-endomorphism of
$\mathbf{H}$. Clearly, $f(x)=\lambda^{M^0}_a(x)$ for all $x\in
M^0$. If $a=0$ then we define a mapping $f:V\rightarrow V$ by
$f(v)=v_i$ for every $i=0,1,\dots,l+1$ and every $v\in V_i$. It is
easy to verify that $f$ is a $\mathcal{P}$-endomorphism of
$\mathbf{H}$ and $f(x)=\lambda^{M^0}_0(x)$ for all $x\in M^0$.
Thus (r2) for $\mathbf{H}$ and $M^0$ is proved.

To prove (r3) consider two distinct $\mathcal{P}$-endomorphisms
$f$ and $g$ of $\mathbf{H}$. We have already proved above that if
$h$ is a $\mathcal{P}$-endomorphism of $\mathbf{H}$ satisfying
$h(e)=0$ then $h(V_i)=\{v_i\}$ for all $i=0,1,\dots,l+1$. Thus we
may assume $f(e),g(e)\in M$ for otherwise $f(e)\ne g(e)$ and would
be done. In the proof of (r1) we established that $f(e),g(e)\in M$
implies $f(U),g(U)\subseteq U$ and, moreover, from $f\ne g$ it
follows that the restrictions $f$ and $g$ to $U$ are distinct. An
application of (r3) to $\mathbf{G}$ and the restrictions of $f$
and $g$ to $U$ completes the proof of (r3) for $\mathbf{H}$.
$\Box$


\vspace{.1in} \noindent\textbf{Definition}. A \emph{normal}
\emph{band} \emph{monoid} is a monoid of the form $M=S^1$ where
$S$ is an arbitrary semigroup satisfying $x^2=x$ and $xuvx=xvux$
for all $x,u,v\in S$. \vspace{.1in}

Every normal band monoid is a subdirect product of monoids from
the five element class $\mathcal{M}$\footnote{This is the class of
subdirectly irreducible normal band monoids, that is, monoids
which can not be realized as a subdirect product.} consisting of
the monoids $M$ where
\begin{itemize}
\item $M$ is a two-element semilattice monoid. \item $M=S^1$ where
$S$ is a two-element left (or right)-zero semigroup -- that is a
semigroup $S=S_L$ satisfying $xy=x$ for all $x,y\in S$ or $S=S_R$
satisfying $xy=y$ for all $x,y\in S$. \item $M= (S^0)^1$ where $S$
is a two-element left (or right)-zero semigroup.
\end{itemize}
The above facts were established in [G]. Lemma 5.7 describes
the $\mathcal{P}$-graphs representing each of the five
aforementioned factors which may appear in a product containing a
normal band monoid.

\paragraph{Lemma 5.8.}For every subdirectly irreducible normal band
monoid $M$ there exists a $\mathcal{P}$-graph $\mathbf{G}$
representing $M$ with $|\mathbf{G}|\leq 17$ and $w(\mathbf{G})\leq
6$.


\paragraph{Proof:}Let $M=(M,\cdot ,e)$ be a subdirectly
irreducible normal band monoid.  If $M$ is a semilattice monoid
then there exists a $\mathcal{P}$-graph $\mathbf{G}$ representing
$M$ with $|\mathbf{G}|=3\leq 17$ and $w(\mathbf{G})=2\leq 6$.

Next assume that $e$ is an outer identity of $M$ and $M\setminus
\{e\}=\{x,y\}$ is a two-element left(or right)-zero semigroup
$S_L$ (or $S_R$, respectively). Now consider the
$\mathcal{P}$-graph $\mathbf{G}=(G=(V,E),\mathcal{P}=\{U_i\mid
i\in I\})$ where $I=\{0,1,x,y\}$, $V=(M\times \{0,1\})\cup
((M\setminus \{e\})\times \{x,y\})$, $U_i=V\cap (M\times \{i\})$
for all $i\in I$ and
\begin{align*} E=&\{\{(z,0),(z,1)\}\mid z\in M\}\cup
\{\{(z,0),(z,i)\}\mid
z\in M\setminus \{e\},\,i\in \{x,y\}\}\cup\\
&\{\{(z,1),(zi,i)\}\mid z\in M,\,i\in \{x,y\}\}.
\end{align*}
Depending on whether $M=(S_L)^1$ or $M=(S_R)^1$ we obtain two
$\mathcal{P}$-graphs $\mathbf{G}=\mathbf{G}_L$ and
$\mathbf{G}=\mathbf{G}_R$ (see Figure 5.1 and 5.2 for $(S_L)^1$ and
$\mathbf{G}_L$). Clearly, $\mathcal{P}$ and $E$ are correctly
defined and $\mathbf{G}$ is a $ \mathcal{P}$-graph with
$|\mathbf{G}|=10\leq 17$ and $w(\mathbf{G})=4\leq 6$.



\begin{figure}
 \centering
 \epsfbox{the-4.5}
 \caption{multiplication table for $(S_L)^1$}
\end{figure}


\begin{figure}
 \centering
 \epsfbox{the-5.2}
 \caption{$\mathcal{P}$-graph $\mathbf{G}_L$ for $(S_L)^1$}
\end{figure}


To prove that $\mathbf{G}_L$ represents $(S_L)^1$ we observe that
all $\mathcal{P}$-endomorphisms of $\mathbf{G}_L$ are of the form
$(u,v)\mapsto(g(u),v)$ where $g$ is either the identity or
$g(e)=g(x)=x$, $g(y)=y$ or $g(e)=g(y)=y$, $g(x)=x$. Similarly the
only $\mathcal{P}$-endomorphisms of $\mathbf{G}_R$ are of the form
$(u,v)\mapsto(g(u),v)$ where $g$ is either the identity or the
constant mapping with value $x$ or $y$.


Finally, consider $M=\{x,y,e,0\}$ where $0$ is an outer zero of
$M$ and $e$ is the outer identity. By Lemma 5.7 there
exists $ \mathcal{P}$-graph representing $M$ with
$|\mathbf{G}|=17$ and $w(\mathbf{G})=6$.
$\Box$

The following theorem summarizes facts about normal band monoids.

\paragraph{Theorem 5.9.}Let $M=(M,\cdot ,e)$ be a normal band
monoid.  Then there exists a $\mathcal{P}$-graph $\mathbf{G}$
representing $M$ such that $|\mathbf{G}|\leq 18|M|$ and
$w(\mathbf{G})\leq 6|M|$. Thus, $\Pi_{\mathcal{NB}}(n)\leq 18n$.


\paragraph{Proof:}Let $\mathcal{M}$ be the class consisting of
subdirectly irreducible normal band monoids. As every normal band
monoid is a subdirect product of monoids from $\mathcal{M}$ we can
apply Corollary 5.5. The statements follows from a
combination of Lemma 5.8 and Corollary 5.5.
$\Box$

Next we give an easy technical lemma about finite cyclic groups.

\paragraph{Lemma 5.10.}For every finite cyclic group $C$
there exists a $\mathcal{P}$-graph $\mathbf{G}$ representing $C$
with $|\mathbf{G}|\leq 3|C|$ and $w(\mathbf{G})=3$.


\paragraph{Proof:}Let $C$ be a finite cyclic group
and let $a\in C$ be a generator of $C$.  Consider a
$\mathcal{P}$-graph $\mathbf{G}=(G=(V,E),\mathcal{P}=\{U_i\mid
i\in I\})$ where $I=\{0,1,2\}$, $ V=C\times I$, $U_i=V\cap
(C\times \{i\})$ for all $i\in I$ and
\begin{eqnarray*}E&=&E_1\cup E_2,\quad\mbox{where}\\
E_1&=&\{\{(z,0),(z,i)\}\mid z\in C,\,i\in \{1,2\}\}\quad\mbox{and}\\
E_2&=&\{\{(z,1),(za,2)\}\mid z\in C\}.
\end{eqnarray*}
Clearly, $\mathcal{P}$ and $E$ are defined so that
$\mathbf{G}$ is a $ \mathcal{P}$-graph with $|\mathbf{G}|=3|C|$,
$w(\mathbf{G})=3$.  Due to the edges of $E_1$ for any
$\mathcal{P}$-endomorphism $f$ of $\mathbf{G}$ there exists a
mapping $g:C\rightarrow C$ such that $f(z,i)=(g(z),i)$ for all
$z\in C$ and $i=0,1,2$. Due to the edges of $E_2$ we infer that
$ag(x)=g(x)a$ holds for all $x\in C$. Since $a$ is a generator of
$C$ and the only mappings that commute with the translations
$\lambda_a=\rho_a$ are translations $\lambda_{a^i}=(\lambda_a)^i$
for all natural numbers $i=0,1,\dots$ we deduce that
$\End_{\mathcal{P}}(\mathbf{G})\cong C$.
$\Box$

\paragraph{Theorem 5.11.}Let $M=(M,\cdot ,e)$ be an Abelian
group. Then there exists a $\mathcal{P}$-graph $\mathbf{G}$
representing $M$ such that $|\mathbf{G}|\leq 4|M|$ and
$w(\mathbf{G})\leq 1+3\log|M|$. Thus, $\Pi_{\mathcal{A}}(n)\leq
4n$.


\paragraph{Proof:}Consider a finite Abelian group $M=(M,\cdot
,e)$. It is well-known that $M$ is a direct product of
finite cyclic groups, say, $$\{M^{(i)}=(M^{(i)},\cdot ,e^{(i)})\mid i\in
I\}.$$ Clearly, we can assume that $|M^{(i)}|>1$ for all $i\in I$
and hence $|M|=\prod_{i\in I}|M^{(i)}|\geq\sum_{i\in I}|M^{(i)}|$
and $|I|\leq\log|M|$. For each $i\in I$ let
$\pi^{(i)}:M\rightarrow M^{(i)}$ be the canonical projection and
set $\mathfrak{F}=\{\pi^{(i)}\mid i\in I\}$, then $\mathfrak{F}$
is a separating family of surjective monoid homomorphisms. By
Lemma 5.10, there exists a family $\mathfrak
{G}=\{\mathbf{G}^{(i)}\mid i\in I\}$ of $\mathcal{P}$-graphs such
that $ \mathbf{G}^{(i)}$ represents $M^{(i)}$,
$|\mathbf{G}^{(i)}|=3|M^{(i)}|$, $w(\mathbf{G}^{(i)})=3$ for all
$i\in I$. We apply Construction 5.2 to obtain
$\mathbf{G}=\Pi (\mathfrak{G},\mathfrak{F},M)$. By (1),
$|\mathbf{G}|=|M| +\sum_{i\in I}3|M^{(i)}|\leq 4|M|$ and
$w(\mathbf{G})=1+\sum_{i\in I}3=1+3I\leq 1+3\log|M|$. By Theorem 5.3, $\mathbf{G}$ represents $M$ and the proof is complete.
$\Box$

Combining Theorems 5.1, 5.9 and 5.11 with
Proposition 5.4 we derive the following bounds.

\paragraph{Theorem 5.12.}Let $n$ be an integer. For semilattice monoids, normal band monoids, and Abelian groups the following bounds hold respectively:



\begin{eqnarray*}\nu_{\mathcal{L}}(n)&\leq & 12n+5\\
\nu_{\mathcal{NB}}(n)&\leq & 42n+5\\
\nu_{\mathcal{A}}(n)&\leq & 4n+12\log n +9. \end{eqnarray*}


Theorem 7 follows immediately from Theorem 5.12. 