\mychapter{Semilattice extension}

This section is devoted to the proof of Theorem 8. We supply the necessary concepts, omitted in Section 5.1, below.
The main concept of this section is that of a strong semilattice of
semigroups.

\vspace{.2in} \noindent\textbf{Definition}. Let $(Y,\cdot )$ be a
semilattice partially ordered by $y\leq z$ if and only if $yz=z$.
Let $\{S_y\mid y\in Y\}$ be a family of pairwise
disjoint semigroups and let $\{\phi_{y,z}:S_y\rightarrow S_z\mid
y,z\in Y,y\leq z\}$ be a family of semigroup homomorphisms such
that
\begin{itemize} \item $\phi_{y,y}$ is the identity mapping
for every $y\in Y$; \item if $x,y,z\in Y$ with $x\leq y\leq z$
then $\phi_{y,z}\circ\phi_{x,y} =\phi_{x,z}$.
\end{itemize}
Let $S=\bigcup_{y\in Y}S_y$ and for $s\in S_y\subseteq S$ and
$t\in S_z\subseteq S$ where $y,z\in Y$ define
$$s\cdot t=\phi_{y,yz}(s)\phi_{z,yz}(t)$$
where the right multiplication is in $S_{yz}$. Then $S$ is a semigroup which is the \textit{strong semilattice of
semigroups $\{S_y\mid y\in Y\}$ determined by $\{\phi_{y,z}\mid
y,z\in Y,y\leq z\}$}. If $\mathcal{C}$ is a class of semigroups
such that $S_y\in \mathcal{C}$ for every $y\in Y$ then we say that
$S$ is a \textit{strong semilattice of $\mathcal{C}$-semigroups.}
\vspace{.2in}

\noindent\textbf{Definition}. For a class $\mathcal{C}$ of
semigroups let $\mathfrak{S}(\mathcal{C})$ be the class of all
finite monoids $M$ of the following form
\begin{itemize}
\item $M$ is a monoid which is a strong semilattice of
$\mathcal{C}$ semigroups; \item $M=S^1$ where $S$ is a strong
semilattice of $\mathcal{C}$-semigroups (here $S$ is not a monoid).
\end{itemize}


Recall that $\mathcal{A}$, $\mathcal{G}$, $\mathcal{RG}$, and $\mathcal{CS}$ are the classes of all
abelian groups, groups, rectangular groups, and completely simple semigroups respectively.

Let  $\mathcal{RG}^1$ be the class of all monoids $M$ of the form
$M=S$ or $M=S^1$ where $S\in\mathcal{RG}$. Similarly, let
$\mathcal{CS}^1$ be the class of all monoids $M$ of the form $M=S$
or $M=S^1$ where $S\in\mathcal{CS}$. \vspace{.2in}

Theorem 8 gives bounds on
$\nu_{\mathfrak{S}(\mathcal{C})}$ where $\mathcal{C}$ is one of
the following four classes $\mathcal{A},\mathcal{G},\mathcal{RG}$,
or $\mathcal{CS}$.

In this section we are going to prove the following more detailed
form of Theorem 8.

\paragraph{Theorem 6.1}Let $M$ be a monoid. Then
\begin{enumerate}
\item if $M\in\mathfrak{S}(\mathcal{A})$ then there exists a
$\mathcal{P}$-graph $ \mathbf{G}$ representing $M$ such that
$|\mathbf{G}|\leq 9|M|$ and $w(\mathbf{G})<3|M|$, thus
$\nu_{\mathfrak{S}(\mathcal{A})}(n)\leq 21n$; \item if $M\in
\mathfrak{S}(\mathcal{G})$ then there exists a $\mathcal{P}$-graph
$ \mathbf{G}$ representing $M$ such that $|\mathbf{G}|\leq
2|M|\sqrt {\log\log|M|}+12|M|$ and $w(\mathbf{G})<5|M|$, thus
$\nu_{\mathfrak{S}(\mathcal{G})}(n)\leq 2n\sqrt {\log\log n}+32n$;
\item if $M\in\mathfrak{S}(\mathcal{RG})$ then there exists a $
\mathcal{P}$-graph $\mathbf{G}$ representing $M$ such that
$|\mathbf{G}|\leq 12|M|+2|M|\sqrt {\log|M|}$ and $w(\mathbf{G})
<3|M|$, thus $\nu_{\mathfrak{S}(\mathcal{RG})}(n)\leq 24n+2n\sqrt
{\log n}$; \item if $M\in \mathfrak{S}(\mathcal{CS})$ then there
exists a $\mathcal{P}$-graph $\mathbf{G}$ representing $M$ such
that $|\mathbf{G}|\leq (2+o(1))|M|^{\frac 76}$ and
$w(\mathbf{G})\leq (4+o(1))|M|$, thus
$\nu_{\mathfrak{S}(\mathcal{A})}(n)\leq (2+o(1))n^{\frac 76}$.
\end{enumerate}


\paragraph{Proof:}
The proof of Theorem 6.1 is based on the special properties
of strong semilattices of semigroups given in Proposition III.7.2
in [P]. From these properties follows a general representation
theorem for strong semilattices of semigroups. Theorem 6.1
is obtained by a substitution of known bounds for the factors from each of the classes in the
representation theorem.

\paragraph{Theorem 6.2}[P] Let $(Y,\cdot )$ be a semilattice and
$S=(S,\cdot )$ be a strong semilattice of $\{S_y\mid
y\in Y\}$ determined by $\{\phi_{y,z}:S_y\rightarrow S_z\mid
y,z\in Y,\, y\leq z\}$. Assume that $0\notin S_y$ for every $y\in
Y$ and let $T_y=S_y$ if $y$ is the greatest element of $Y$ under
$\le$ and $T_y=(S_ y)^0$ otherwise. For $y\in Y$ let us define a
mapping $f_y:S\rightarrow T_y$ such that
$$f_y(s)=\left\{%
\begin{array}{ll}
  \phi_{z,y}(s)&\text{ if }s\in S_z\text{ for }z\in
Y\text{ with }z\le y \\
  0_y&\text{ if }s\in S_z\text{ for }z\in Y\text{ with }z\not\leq
y. \\
\end{array}%
\right.$$ Then $\{f_y:S\rightarrow T_y\mid y\in Y\}$ is a
separating family of surjective homomorphisms.


Combining Construction 5.2 with Theorem 6.2 yields
the following theorem.



\paragraph{Theorem 6.3} Let $(Y,\cdot )$ be a semilattice and $S=(S,\cdot)$
be a strong semilattice of $\{S_y\mid y\in Y\}$. Then
\begin{enumerate} \item if $S=M$ is a monoid and if there exists a
family $\{\mathbf{G}_y\mid y\in Y\}$ of $\mathcal{P}$-graphs such
that $\mathbf{G}_y$ represents $S_y$ for every $y\in Y$ then there
exists a $\mathcal{P}$-graph $\mathbf{G}$ representing $S$ such
that
$$|\mathbf{G}|\leq |M|+3|Y|+\sum_{y\in Y}(|\mathbf{G}_y|+w(\mathbf{G}_y))\leq
4|S|+2\sum_{y\in Y}|\mathbf{G}_y|$$ and
$w(\mathbf{G})=1+2|Y|+\sum_{y\in Y}w(\mathbf{G}_y)$; \item if
there exists a family $\{\mathbf{G}_y\mid y\in Y\}$ of
$\mathcal{P}$-graphs such that $\mathbf{G}_y$ represents $(S_y)^1$
for every $y\in Y$ then there exists a $\mathcal{P}$-graph
$\mathbf{G}$ representing $M=S^1$ such that
$$|\mathbf{G}|\leq |M|+3|Y|+\sum_{y\in Y}(|\mathbf{G}_y|+w(\mathbf{G}_y))\leq
4|M|+2\sum_{y\in Y}|\mathbf{G}_y|$$ and $w(\mathbf{G})
=1+2|Y|+\sum_{y\in Y}w(\mathbf{G}_y)$.
\end{enumerate}


\paragraph{Proof:}To prove the theorem we will apply Construction 5.2 and Theorem 5.3.
Assume that  $\{f_y:M\rightarrow S_y^0\mid y\in Y\}$ in Case 1)
and $\{f_y:M\rightarrow (S_y^1)^0\mid y\in Y\}$ in Case 2) is a
separating family of monoid homomorphisms. By assumption, there
exists a family $\{\mathbf{G}_y\mid y\in Y\}$ of
$\mathcal{P}$-graphs such that $\mathbf{G}_y$ represents $S_y$ for
every $y\in Y$ in Case 1) and $\mathbf{G}_y$ represents $S_y^1$
for every $y\in Y$ in Case 2). By Lemma 5.7, there exists a
family $\{\mathbf{H}_y\mid y\in Y\}$ of $\mathcal{P}$-graphs such
that  $\mathbf{H}_y$ represents $S_y^0$ for every $y\in Y$ in Case
1) and $\mathbf{H}_y$ represents $(S_y^1)^0$ for every $y\in Y$ in
Case 2). We apply Construction 5.2 on the families
$\{\mathbf{H}_y\mid y\in Y\}$ and $\{f_y\mid y\in Y\}$ to obtain a
$\mathcal{P}$-graph $\mathbf{G}$ such that
$$|\mathbf{G}|=|M|+\sum_{y\in Y}|\mathbf{H}_y|=|M|+3|Y|+\sum_{y\in Y}(|\mathbf{G}_y|+w(\mathbf{G}_y))$$ and $w(\mathbf{G})
=1+2|Y|+\sum_{y\in Y}w(\mathbf{G}_y)$. By Theorem 5.3,
$\mathbf{G}$ represents $M$. Thus it remains only to find a
separating family of monoid homomorphisms $\{f_y:M\rightarrow
S_y^0\mid y\in Y\}$ in Case 1) and $\{f_y:M\rightarrow
(S_y^1)^0\mid y\in Y\}$ in Case 2).

Consider Case 1). By Theorem 6.2, there exists a separating
family $\{f'_y:M\rightarrow T_y\mid y\in Y\}$ of surjective
semigroup homomorphisms where either $T_y=S_y$ or $T_y=(S_y)^0$.
Since $f'_y$ is a surjective semigroup homomorphism and $M$ is a
monoid we infer that $T_y$ is a monoid and $f'_y$  is a monoid
homomorphism and thus there exists a separating family of monoid
homomorphisms $\{f_y:M\rightarrow S_y^0\mid y\in Y\}$ and the
proof of Case 1) is complete.

Consider Case 2). By Theorem 6.2, there exists a separating
family $\{f'_y:M\rightarrow T_y\mid y\in Y\}$ of surjective
semigroup homomorphisms where either $T_y=S_y$ or $T_y=(S_y)^0$.
Let us define $f_y:S^1\rightarrow(S_y^1)^0$ for every $y\in Y$
such that $f_y(s)=f'_y(s)$ for all $s\in S$ and $f_y(1)=1$. Then
$\{f_y\mid y\in Y\}$  is a separating family because
$f_y^{-1}(1)=\{1\}$ and $f_y$ is a monoid homomorphism because
$f'_y$  is a semigroup homomorphism and $1$ is an outer identity
of $S^1$ and of $(S_y^1)^0$. Hence the proof of Case 2) follows.
$\Box$

Next we prove an auxiliary lemma.


\paragraph{Lemma 6.4}If $S$ is a strong semilattice of groups (or abelian groups) then
$S^1$ is also a strong semilattice of groups (or abelian
groups, respectively).


\paragraph{Proof:}Assume that $S$ is a strong semilattice of $\{S_y\mid y\in Y\}$ determined
by $\{\phi_{y,z}:S_y,\rightarrow S_z\mid y,z\in Y,\,y\le z\}$
where $(Y,\cdot)$ is a semilattice, $S_y$ is a group for all
$y\in Y$, and $e_y$ is the identity in $S_y$. Let $a$ be an element with $a\notin Y$, then
$(Y\cup\{a\},\cdot)$ where $ay=ay=y$ for all $y\in Y\cup\{a\}$ is a
semilattice. Let $S_a=e_a$ be the singleton group.
For every $y\in Y\cup\{a\}$ let $\phi_{a,y}$ be the mapping such
that $\phi(e_a)=e_y$. Then $\phi_{a,y}:S_a\rightarrow S_y$ is a
group homomorphism for all $y\in Y\cup\{a\}$. Clearly, the family
$\{\phi_{y,z}\mid y,z\in Y\cup\{a\},\,y\leq z\}$ satisfies the
conditions on a family homomorphisms from the definition of strong
semilattice of semigroups. Let $T$ be a strong semilattice of
$\{S_y\mid y\in Y\cup\{a\}\}$ determined by $\{\phi_{y,z}\mid
y,z\in Y\cup\{a\},\,y\leq z\}$. Thus $T$ is a strong semilattice
of groups and if $S_y$ is an abelian group for all $y\in Y$ then
$T$ is a strong semilattice of abelian groups.

It remains to prove that $T$ is isomorphic to $S^1$. Clearly,
$S\subseteq T$ and let $f:S^1\rightarrow T$ be a mapping such that
$f(s)=s$  for all $s\in S$ and $f(1)=e_a$. Then $f$ is a bijection
and by the definition of a strong semilattice of semigroups
$f(st)=st=f(s)f(t)$ for all $s,t\in S$. For all $y\in Y\cup\{a\}$
we have $a\leq y$, $\phi_{a,y}(e_a)=e_y$ and $\phi_{y,y}$ is the
identity of $S_y$. Thus for every $s\in S_y$ we infer that
$e_as=se_a=s$. Since $1$ is the identity of $S^1$ we conclude that
$f$ is a semigroup isomorphism and the proof follows.
$\Box$

Finally, to complete the proof of Theorem 6.1 we apply
Theorem 6.3 to the four classes of monoids. Let
$\mathcal{C}$ be one of the following classes of semigroups --
abelian groups $\mathcal{A}$, groups $\mathcal{G}$, rectangular
groups $\mathcal{RG}$, or completely simple semigroups
$\mathcal{CS}$. By the definition of $\mathfrak{S}(\mathcal{C})$,
if $M\in\mathfrak{S}(\mathcal{C})$ then $M$ is a strong
semilattice of semigroups $\{S_y\mid y\in Y\}$ where $S_y\in
\mathcal{C}$ for all $y\in Y$ or $M=S^1$ where $S$ is a strong
semilattice of semigroups $\{S_y\mid y\in Y\}$ where
$S_y\in\mathcal{C}$ for all $y\in Y$. In the first case, if there
exists a family $\{\mathbf{G}_y\mid y\in Y\}$ of
$\mathcal{P}$-graphs such that $\mathbf{G}_y$ represents
$\mathcal{S}_y$ for all $y\in Y$ then, by Theorem 6.3(1),
there exists a $\mathcal{P}$-graph $\mathbf{G}$ such that
$\mathbf{G}$ represents $M$ and
\begin{eqnarray*}|\mathbf{G}|&\leq&|M|+3|Y|+\sum_{y\in Y}(|\mathbf{G}_y|+w(\mathbf{G}_y))\\
w(\mathbf{G})&\leq&1+2|Y|+\sum_{y\in
Y}w(\mathbf{G}_y).\end{eqnarray*} In the second case, if there
exists a family $\{\mathbf{G}_y\mid y\in Y\}$ of
$\mathcal{P}$-graphs such that $\mathbf{G}_y$ represents
$\mathcal{S}_y^1$ for all $y\in Y$ then, by Theorem 6.3(2),
there exists a $\mathcal{P}$-graph $\mathbf{G}$ such that
$\mathbf{G}$ represents $M$ and
\begin{eqnarray*}|\mathbf{G}|&\leq&|M|+3|Y|+\sum_{y\in Y}(|\mathbf{G}_y|+w(\mathbf{G}_y))\\
w(\mathbf{G})&\leq&1+2|Y|+\sum_{y\in
Y}w(\mathbf{G}_y).\end{eqnarray*} If $\mathcal{C}=\mathcal{A}$ or
$\mathcal{C}=\mathcal{G}$ then, by Lemma 6.4, we can
consider only the first case and used
$\mathcal{P}$-representations of groups or abelian groups. If
$\mathcal{C}=\mathcal{RG}$ (or $\mathcal{C}=\mathcal{CS}$) then in
the first case $S_y\in(\mathcal{RG})^1$ (or
$S_y\in(\mathcal{CS})^1$) for all $y\in Y$ because $S_y$ is a
monoid for all $y\in Y$ and in the second case
$S_y^1\in(\mathcal{RG})^1$ (or $S_y^1\in(\mathcal{CS})^1$) for all
$y\in Y$. Thus it suffices to use $\mathcal{P}$-representations of
monoids from $(\mathcal{RG})^1$ (or $(\mathcal{CS})^1$,
respectively).


The proof is divided into four parts depending which class of
semigroup is being considered. If $M=Y$ then $M$ is a semilattice
monoid and Proposition 5.6 gives the required
$\mathcal{P}$-graph. Thus we can assume that $M\ne Y$ and thus
$|Y|<|M|$.
\begin{itemize}
\item Suppose $\mathcal{C}=\mathcal{A}$. By Theorem 5.11, we
can assume that $|\mathbf{G}_y|\leq 4|S_y|$ and $w(\mathbf{G}_y)
\leq 1+\log(|S_y|)\leq |S_y|$ for all $y\in Y$. Thus
$|\mathbf{G}_y|+w(\mathbf{G}_y)\leq 5|S_y|$ and hence
$$|\mathbf{G}|\leq |M|+3|Y|+\sum_{y\in Y}(\mathbf{G}_y+w(\mathbf{G}_y)\leq 4|M|+\sum_{y\in Y}5|S_y|\leq 9|M|.$$ Moreover, $\sum_{y\in Y}w(
\mathbf{G}_y)\leq |M|$ and hence $w(\mathbf{G})\leq 3|M|$. From
Theorem 5.1 it follows that
$\nu_{\mathfrak{S}(\mathcal{A})}(n)\leq 21n$.

\item Suppose $\mathcal{C}=\mathcal{G}$. By Theorem 3, we can assume
that
\begin{eqnarray*}|\mathbf{G}_y|&\leq&
2|S_y|(\sqrt {\log\log(|S_y|+1)}+2)\quad\text{and}\\
w(\mathbf{G}_y )&\leq&2+2\sqrt {\log\log(|S_y|+1)}\end{eqnarray*}
for all $y\in Y$. Thus $$|\mathbf{G}_y|+w(\mathbf{G}_y)\leq
(2|S_y|+2)\sqrt {\log\log (|S_y|+1)}+4|S_y|+2.$$ From
$x\geq\log(x+1)$ for all $x\geq 1$ we infer
$$\sum_{y\in Y}\sqrt{\log\log(|S_y|+1)}\leq \sum_{y\in Y}\sqrt{|S_y|}\leq \sum_{y\in Y}|S_y|\leq M.$$
Hence $\sum_{y\in Y}(|\mathbf{G}_y|+w(\mathbf{G}_y))\leq
8|M|+2|M|\sqrt{\log\log(|M|+1)}$ and consequently,
$|\mathbf{G}|\leq 2|M|\sqrt{\log\log(|M|+1)}+12|M|$. Moreover, we
conclude that $\sum_{y\in Y}w (\mathbf{G}_y)\leq2|Y|+2|M|$ and
hence $w(\mathbf{G})\leq 6|M|$. From Theorem 5.1 it follows
that $\nu_{\mathfrak{S}(\mathcal{G})}(n)\leq 2n\sqrt {\log\log
n}+36n$.

\item Suppose $\mathcal{C}=\mathcal{RG}$. Since
$S_y\in(\mathcal{RG})^1$ for all $y\in Y$, by theorem 4, we can assume
that $$|\mathbf{G}_y|\leq 2|S_y|(\sqrt
{3+\log|S_y|})\quad\text{and}\quad w(\mathbf{G}_y)\leq 2\sqrt
{3+\log|S_y|}$$ for all $y\in Y$. Thus
$|\mathbf{G}_y|+w(\mathbf{G}_y)\leq (2|S_y|+2)(\sqrt
{3+\log|S_y|})$. Since
$$\sum_{y\in Y}\sqrt{3+\log|S_y|}\leq \sum_{y\in Y}\sqrt{|S_y|+3}\leq \sum_{y\in Y}(|S_y|+3)\leq 4|M|$$
we infer that $|\mathbf{G}|\leq 2|M|\sqrt {3+\log|M|}+12|M|$.
Moreover, $w(\mathbf{G})\leq 3|M|$. From Theorem 5.1 it
follows that $\nu_{\mathfrak{S}(\mathcal{RG})}(n)\leq 2n\sqrt
{\log n}+ 24n$.

\item Suppose $\mathcal{C}=\mathcal{CS}$. Since
$S_y\in(\mathcal{CS})^1$ for all $y\in Y$, by Theorem 6, we can assume
that $|\mathbf{G}_y|\leq (2+o(1))|S_y|^{\frac 76}$ and
$w(\mathbf{G}_y)\leq (2 +o(1))|S_y|^{\frac 16}$ for all $y\in Y$.
Thus $|\mathbf{G}_y|+w(\mathbf{G}_y)\leq (2+o(1))|S_y|^{\frac 76}$
and hence $|\mathbf{G}|\leq (2+o(1))|M|^{\frac 76}$. From
$|S_y|^{\frac 16}<|S_y|$ for all $y\in Y$ we infer that
$\sum_{y\in Y}w(\mathbf{G}_y)\leq (2+o(1))|M|$ and hence
$w(\mathbf{G})\leq (4+o(1))|M|$. From Theorem 7 it
follows that $\nu_{\mathfrak{S}(\mathcal{CS})}(n)\leq
(2+o(1))n^{\frac 76}$.
\end{itemize}
$\Box$


Summarizing we have just proved the following bounds:

\paragraph{Corollary 6.5}
\begin{eqnarray*}
\Pi_{\mathfrak{S}(\mathcal{A})}(n)\leq 9n,&\quad&
\Pi_{\mathfrak{S}(\mathcal{G})}(n)\leq 2n\sqrt {\log\log n}+12n,\\
\Pi_{\mathfrak{S}(\mathcal{RG})}(n)\leq 2n\sqrt {\log
n}+12n,&\quad&
\Pi_{\mathfrak{S}(\mathcal{CS})}(n)=(2+o(1))n^{\frac
76}.\end{eqnarray*}


\paragraph{Remark:} One of the important
generalizations of groups are regular semigroups. By [P], every
commutative regular semigroup is a strong semilattice of abelian
groups and, thus, Theorem 6.1(1) gives an estimate on the
size of a finite graph with a given commutative regular monoid as
its endomorphism monoid. \vspace {.2 in}




