\mychapter{Special Classes of Monoids}


\section {Groups and Generalizations}
%\end{section}


For a given monoid $\mathbf{M}$ there may be several choices for
the map $\phi$, other than a singleton map, yielding
$\End(G(\mathbf{M},\phi))\cong\mathbf{M}$. In some cases we can
exploit the algebraic structure of a monoid to construct a more
``efficient" map. We will require the following technical
proposition.

\paragraph{Proposition 4.1.} For every finite non-empty set $A$ there
exists a family $\{A_i\mid i\in I\}$ of subsets of $A$ such that
$\{a\}=\bigcap \{A_i\mid i\in I,\,a\in A_i\}$ for all $a\in A$ and
$ |I|=2\lceil\log|A|\rceil$.

\paragraph{Proof:} Let $k=\lceil\log|A|\rceil$. Then there exists an injective mapping
$f:A\rightarrow \{0,1\}^k$ for $k=\lceil\log|A|\rceil$. For each
projection $\pi_i:\{0,1\}^k\rightarrow \{0,1\}$ with $i\in [1,k]$
let $A_{ij}=(\pi_i\circ f)^{-1}(j),~j=0,1$. Then the family
$\{A_{ij}\mid i\in [1,k],j=0,1\}$ has the required properties.
$\Box$

\paragraph{Proposition 4.2.} Let $\mathbf{H}$ be a group with a set
$A$ of generators. Then there exists a family
$\mathcal{F}=\{B_{ij}\mid (i,j)\in{[t]\choose 2}\}$ of subsets of
$A$ such that $\End ( G(\mathbf{H},\phi ))$ is isomorphic to
$\mathbf{H}$ and $t\leq 2\sqrt{\lceil\log|A|\rceil}+2$.

\paragraph{Proof:} We show that condition $(\mathbf{P})$, required for
Proposition 3.4(iii), is satisfied by a suitable choice of
$B_{ij}$. Choose $x,x'\in\mathbf{H}$. Since $\mathbf{H}$ is a
group $R(x,x')$ is a singleton. Suppose, that $R(x,x')=\{a_0\}$. By
Proposition 4.1, there exists a family $\mathcal{F}=\{B_{ij}\mid
(i,j)\in{[t]\choose 2}\}$ of subsets of $A$ such that
$\{a\}=\bigcap \{B_{ij}\mid B_{ij}\in\mathcal{F},\,a\in B_{ij}\}$
for all $a\in A$. Hence, for $a\in A\setminus\{a_0\}$ there exists
$(i,j)\in {[t]\choose 2}$ with $a\in B_{ij}$ and $a_0\notin
B_{ij}$. Then $a\in B(x,x')$ and as $a\in A\setminus\{a_0\}$ was
arbitrary $B(x,x')=A\setminus \{a_0\}=A\setminus R(x,x')$, that
is, condition $(\mathbf{P})$ is satisfied. Hence, by Proposition
3.4, $\End (G(\mathbf{H},\phi ))\cong\mathbf{H}$. Since in order
to use the construction we require ${t\choose 2}\geq
|\mathcal{F}|=2\lceil\log|A|\rceil$ it suffices to take $t\leq
2\sqrt{\lceil\log|A|\rceil}+2$. $\Box$ \vspace {.1 in}

Let $\mathcal{G}$ be the family of finite groups.

\paragraph{Theorem 3.}$\nu_{\mathcal{G}}(m)\leq (2+o(1))m\sqrt
{\log\log m}$.
\paragraph{Proof:} We show that $\nu_{\mathcal{G}}(m)\leq
(2+o(1))m\sqrt {\log\log m}$. If $\mathbf{H}$ is an $m$-element
group then there exists a set $A$ of generators with
$|A|\leq\lceil\log m\rceil$ and, by a combination of Propositions
3.4 and 4.2, there exists a graph $G$ on
$(m+4)(2\sqrt{\lceil\log\log m\rceil}+3)+5=(2+o(1))m\sqrt {\log\log
m}$ vertices such that $\End(G)\cong\mathbf{H}$, as required.
$\Box$ \vspace {.1 in}

Next we generalize Theorem 3 to a class of monoids generalizing
groups. Let $B$ and $C$ be non-empty sets and $\mathbf{H}$ be a
group. Then a semigroup $\mathbf{S}=\mathcal{R}
(B,\mathbf{H},C)=(B\times H\times C,\cdot )$ where
$(b,h,c)(b',h',c')=(b,hh',c')$ is called a \emph{rectangular}
\emph{group} (see monographs of semigroups [CP] and [H]). Clearly,
any rectangular group is isomorphic to a product of a non-empty
left-zero semigroup (that is a semigroup satisfying the identity
$xy=x$), a group and a right-zero semigroup (that is a semigroup
satisfying the identity $xy=y$). We shall consider monoids of the
form $\mathbf{M}=\mathbf{S}^1$ where $\mathbf{S}$ is a rectangular
group. First we recall a well-known folklore statement describing
generating sets of rectangular groups (the proof is an easy
exercise).

\paragraph{Lemma 4.3.} Let $\mathbf{M}=\mathbf{S}^1$ be a monoid where
$\mathbf{S}=\mathcal{R}(B,\mathbf{H},C)$ is a rectangular group.
Then $U\subseteq B\times H\times C$ is a set of generators if and
only if there exists a set $A$ of generators of $\mathbf{H}$
satisfying: \begin{itemize} \item[(a)] for every $b\in B$ there
exist $h\in H$ and $c\in C$ with $(b,h, c)\in U$; \item[(b)] for
every $c\in C$ there exist $h\in H$ and $b\in B$ with $(b,h, c)\in
U$; \item[(c)] for every $a\in A$ there exist $b\in B$ and $c\in
C$ with $(b,a,c)\in U$. $\Box$
\end{itemize}
\vspace {.1 in}

Using this lemma we obtain the following result.

\paragraph{Proposition 4.4.} For every finite rectangular group
$\mathbf{S}=\mathcal{R}(B,\mathbf{H},C)$ and for every set $A$ of
generators of $\mathbf{H}$, there exist a set $U$ of generators of
$\mathbf{M}=\mathbf{S}^ 1$ and a family $\{B_{ij}\mid (i,j)\in
{[t]\choose 2}\}$ of subsets of $U$ such that $\End
(G(\mathbf{M},\phi ))$ is isomorphic to $\mathbf{M}$ and $t\leq
2\sqrt {q}+2$ where $q=\lceil\log|B|\rceil +\lceil\log|A|\rceil
+\lceil\log|C|\rceil$.

\paragraph{Proof:} Choose $b_0\in B$, $c_0\in C$. Let $e$ be the unity of $\mathbf H$ and
let $U=U_1\cup U_2\cup U_3$ where
\begin{align*}
U_1&=\{(b,e,c_0)\mid b\in B\},\\U_2&=\{(b_0,a,c_0)\mid a\in A\},\\
U_3&=\{(b_0,e,c)\mid c\in C\}.\end{align*} By Lemma 4.3, $U$ is a
set of generators of $\mathbf{M}$.  By Proposition 4.1, there
exist families $\{B_i\mid i\in I_1\}$ of subsets of
$\{(b,e,c_0)\mid b\in B\}$, $\{C_i\mid i\in I_2\}$ of subsets of
$\{(b_0,e,c)\mid c\in C\}$ and $ \{A_i\mid i\in I_3\}$ of subsets
of $\{(b_0,a,c_0)\mid a\in A\}$ such that \begin{itemize} \item
$\{(b,e,c_0)\}=\bigcap \{B_i\mid i\in I_1,\, (b,e,c_0)\in B_i\}$
for all $b\in B$; \item $\{(b_0,e,c)\}=\bigcap \{C_i\mid i\in
I_2,\,(b_0,e, c)\in C_i\}$ for all $c\in C$; \item
$\{(b_0,a,c_0)\}=\bigcap \{A_i\mid i\in I_3,\,(b_0,a,c_0)\in
B_i\}$ for all $ a\in A$,\end{itemize} where
$|I_1|=2\lceil\log|B|\rceil$, $|I_2|=2\lceil\log|C|\rceil$, and $
|I_3|=2\lceil\log|A|\rceil$. Next we prove that the family
$$\{B_{ij}\mid (i,j)\in {[t] \choose 2}\}=\{B_i\mid i\in I_1\}\cup
\{C_i\mid i\in I_2\}\cup \{A_i\mid i\in I_3\}$$ with
$t=\lceil2\sqrt{q}+1\rceil$ where $$q=\lceil\log |B|\rceil
+\lceil\log|A|\rceil +\lceil\log|C|\rceil$$ yields
$\End(G(\mathbf{M},\phi))\cong\mathbf{M}$. Clearly, $|{t\choose
2}|\geq |I_1|+|I_2|+|I_ 3|$. Observe that for all $u\in U$
\begin{equation}\{u\}=\bigcap \{B_{ij}\mid (i,j)\in {[t]\choose
2},\,u\in B_{ij}\}.\end{equation}

To complete the proof, by Lemma 3.5, we will verify condition
$(\mathbf{P})$. We show that for all $x,x'\in (B\times H\times
C)\cup \{1\}$
\begin{equation}B(x,x')=U\setminus
R(x,x').\end{equation}

By Remark 2, it is sufficient to show that $U\setminus
R(x,x')\subseteq B(x,x')$.


First observe that if $|R(x,x')\cap U|\leq1$ then, by (1), for
every $u\in U\setminus R(x,x')$ there exists
$(i,j)\in\binom{[t]}2$ with $u\in B_{ij}$ and $B_{ij}\cap
R(x,x')=\emptyset$. Thus equation (2) holds. To complete the
argument we must consider the case $|R(x,x')\cap U|>1$. Therefore we
describe $R(x,x')$ for $x,x'\in X$. Clearly,

\begin{displaymath}R(x,x')=\left\{\begin{array}{ll}\{x'\}&\text{ if }x=1,\\
\emptyset&\text{ if }x\ne 1\text{ and }x'=1\text{\ or}\\
&\text{\ }x=(b,h,c),x'=(b',h',c'),\,b\ne b',\\
\{(\bar{b},h^{-1}h',c')\mid\bar{b}\in B\}&\text{ if
}x=(b,h,c)\text{ and
}x'=(b,h',c').\end{array}\right.\end{displaymath}

Observe that $|R(x,x')|>1$ only if $x=(b,h,c)$ and $x'=(b,h',c')$.
Next observe that if $c'\ne c_0$, then, by the definition of $U$,
$R(x,x')\subseteq U_3$ and hence $|R(x,x')\cap U|\leq 1$ (since
$c'$ in $R(x,x')$ is fixed). Similarly, if $c'=c_0$ and
$h^{-1}h'\ne e$ we obtain $R(x,x')\subseteq U_2$ and hence
$|R(x,x')\cap U|\leq 1$ holds (since $h^{-1}h'$ in $R(x,x')$ is
fixed) as well. Thus $|R(x,x')\cap U|>1$ if and only if $c'=c_0$
and $h^{-1}h'=e$ (this is equivalent to $h=h'$) in which case
$R(x,x')=U_1$. Consequently (since $\{(b_0,e,c_0)\}=U_1\cap
U_2\cap U_3$)
$$U\setminus R(x,x')=U_2\cup U_3\setminus \{(b_0,e,c_0)\}.$$
If $u=(b_0,e,c)\in U_3\setminus\{(b_0,e,c_0)\}$ then, by the
property of $\{C_i\mid i\in I_2\}$, there exists
$(i,j)\in\binom{[t]}2$ with $u\in B_{ij}\subseteq\{(b_0,e,c)\mid
c\in C\}$ and $(b_0,e,c_0)\notin B_{ij}$. Hence $B_{ij}\cap
R(x,x')=\emptyset$ and thus $u\in B(x,x')$. If $u=(b_0,a,c_0)\in
U_2\setminus \{(b_0,e,c_0)\}$ then, by the property of $\{A_i\mid
i\in I_3\}$, there exists $(i,j)\in\binom{[t]}2$ with $u\in
B_{ij}\subseteq\{(b_0,a,c_0)\mid a\in A\}$ and $(b_0,e,c_0)\notin
B_{ij}$. Hence $B_{ij}\cap R(x,x')=\emptyset$ and thus $u\in
B(x,x')$ and (2) holds. $\Box$

\vspace{.1 in}



Let $\mathcal{R}\mathcal{G}$ denote the class of monoids
$\mathbf{M}=\mathbf{S}^ 1$ where $\mathbf{S}$ is a finite
rectangular group.


\paragraph{Theorem 4.}For all $m,~\nu_{\mathcal{R}\mathcal{G}}(m)\leq (
2+o(1))m\sqrt {\log m}$.

\paragraph{Proof:} We need to show that $\nu_{\mathcal{R}\mathcal{G}}(m)
\leq (2+o(1))m\sqrt {\log m}$. If $\mathbf{M}=\mathbf{S}^1$ is a
monoid on an $m$-element set where
$\mathbf{S}=\mathcal{R}(B,\mathbf{H},C)$ is a rectangular group
then, by Propositions 4.4 and 3.4, there exists a graph $G$ on a
set of size $(m+4)(2\sqrt {q}+3)+5$ with $q=\lceil\log|B|\rceil
+\lceil\log|A|\rceil +\lceil\log|C|\rceil$ where $A$ is a set of
generators of $\mathbf{H}$ such that $\End(G)$ is isomorphic to
$\mathbf{M}$. Clearly, $ q\leq 3+\log m$ and, hence, $(m+4)(2\sqrt
{\log m+3}+3)+5\leq (2+o(1))m\sqrt {\log m}$, from which the
statement follows. $\Box$ \vspace{.1 in}

We recall that for the class $\mathcal{R}\mathcal{Z}$ of all
monoids $\mathbf{M} =\mathbf{R}^1$ where $\mathbf{R}$ is a finite
right-zero semigroup (i.e. $xy=y$ for all elements $x$ and $y$)
one can show $\nu_{\mathcal{R}\mathcal{Z}}(m)\leq 6m+9$. This
follows from the construction in the proof of Theorem 3 in [KR3].

\vspace{.1 in}

For a natural number $k\geq 1$, we say that a monoid
$\mathbf{M}=(X,\cdot ,e)$ with a set of generators $A$ is
\emph{weakly} $k$-\emph{right} \emph{cancellative} if $|\{a\in
A\mid xa=x'\} |\leq k$ for all $x,x'\in X$. Recall that a finite
monoid is a group if and only if it is $1$-right cancellative. In
this sense it is a generalization of a group.

\paragraph{Proposition 4.5.} Let $\mathbf{M}=(X,\cdot ,e)$ with
$|X|=m$ be a finite weakly $k$-right cancellative monoid with
respect to a set of generators $A$. Then there exists a family
$\{B_{ij}\mid (i,j)\in {[t]\choose 2}\}$ of subsets of $A$ such
that $\End (G(\mathbf{M},\phi ))$ is isomorphic to $\mathbf{M}$
with $t=\lceil\sqrt{2|A|}+1\rceil$.

Moreover, for $s=\min \{m^2|A|,{|A|\choose k}|A|\}$ if $|A|\geq
(k+1)e\ln s$ then $t\leq \sqrt {2(k+1)e\ln s }+1$.

\paragraph{Proof:} We show that there exists a
family of subsets of $A$ satisfying condition $(\mathbf{P})$. Then
we can apply Proposition 3.4. Specifically, we show that, with $t$
as above, there exists a family $\{B_{ij}\mid (i,j)\in {[t]
\choose 2}\}$ such that for every pair $x,x'\in X$ and every $a\in
A$ with $a\notin R(x,x')$ there exists $(i,j)\in {[t]\choose 2}$
with

\begin{itemize}\item[(i)] $a\in B_{ij}$; \item[(ii)] $B_{ij}\cap R(x,x')
=\emptyset$. \end{itemize} \vspace{.1 in}

First, observe that if $t=\lceil\sqrt{2|A|}+1\rceil$ then
${t\choose 2}\geq |A|$ and we can satisfy the above conditions
with each $B_{ij}$ a singleton, that is, by taking $B_{ij}=\{a\}$
where $a$ runs through $A$ and $(i,j)$ runs through
${[t]\choose2}$.

If, moreover $|A|\geq (k+1)e\ln s$ we can improve the bound on $t$
using the following probabilistic argument: for each $(i,j)\in
{[t]\choose 2}$ a set $B_{ij}$ is a random subset of $A$ obtained
by placing each $a\in A$, randomly, in $B_{ij}$ with probability
$\frac {1}{k+1}$. The choices are made independently for
$(i,j)\in\binom{[t]}2$. Fix a set $R\subseteq A$ with $|R|\leq k$
and $a\in A\setminus R$. For each $(i,j)\in {[t]\choose 2}$ let
$E_{i j}$ denote the event that $a\in B_{ij}$ and $R\cap
B_{ij}=\emptyset$. Since

$$\Prob(R\cap B_{ij}=\emptyset )=\left(1-\frac 1{k+1}\right)^{|R|}\geq \left(1-\frac
1{k+1}\right)^k\geq\frac {1}{e}$$ we conclude that
$\Prob(E_{ij})\geq\frac 1{(k+1)e}$ which, in turn, yields
$$\Prob(\bigwedge_{1\le i<j\le t}\neg E_{ij})\leq \left(1-\frac {1}{(k+1)
e}\right)^{{t\choose 2}}~~~~~~(\ast)$$ In order to ensure
condition $(\mathbf{P})$ we need to satisfy $\bigwedge_{1\le
i<j\le t}\neg E_{ij}$ for all $R=R(x,x')$ and $a\in A\setminus
R(x,x')$. We consider two cases:\begin{itemize}\item[\textbf{Case
1.}] If $m^2< {|A|\choose k}$ then, in view of $(\ast)$, we need
$$\left(1-\frac 1{(k+1) e}\right)^{{t\choose
2}}m^2|A|<e^{-\frac{{t\choose 2}}{(k+1)e}}m^2|A|<1$$ which is
satisfied if $t\geq \sqrt {2(k+1)e\ln (m^2|A|)}+1$.
\item[\textbf{Case 2.}] If $m^2\geq {|A|\choose k}$ we use the
fact that $\mathbf{M}$ is weakly $k$-right concellative with
respect to the set of generators $A$. In order to verify condition
$(\mathbf{P})$, it suffices to show conditions (i) and (ii) hold
with $\{R(x,x')\mid x,x'\in X\}$ replaced by the broader family
${[A]\choose k}$, the set of all $k$-tuples of $A$. This is because
for each $x,x'$ and $a\notin R(x,x')$ we may verify (i) and (ii)
for $R\in {A\choose k}$ with $a\notin R$ and $R(x,x')\subseteq R$.
Thus, we need
$$\left(1-\frac 1{(k+1) e}\right)^{{t\choose 2}}{|A|\choose k}|A|<1$$
which is satisfied if $t\geq \sqrt {2(k+1)e\ln ({|A|\choose
k}|A|)}+1$. $\Box$\end{itemize} \vspace {.1 in}

For a natural number $k\geq 1$, let $\mathcal{C}_k$ consist of all
finite, weakly $k$-right cancellative monoids.


\paragraph{Theorem 5.}For all $m,~\nu_{\mathcal{C}_k}(m)\leq (5+o(1))m\sqrt {k\ln m}$.

\paragraph{Proof:} We will show that $\nu_{\mathcal{C}_k}(m)\leq
5m\sqrt {k\ln m}$ for $m\geq m_0$. By Proposition 3.4, there exists
a graph $G$ with endomorphism monoid $\mathbf{M}$ on at most
$(t+1)(m+4)$ vertices. Since $\ln s\leq 3\ln m$, Proposition 4.5
gives $t\leq \sqrt {6(k+1)e\ln m+1}$. Consequently, since $k\geq
2$ implies $\sqrt {6e(k+1)}<5\sqrt {k}$ we get, for sufficiently
large $m$, that $\nu_{\mathcal{C}_k}(m)\leq (m+4)(t+1)< 5m\sqrt
{k\ln m}$. $\Box$




\section {Completely Simple Monoids}
%\end{section}


The aim of this section is to prove Theorem 6. One of the most
important classes of semigroups generalizing groups is the class
of completely simple semigroups, see [CP].

\paragraph{Definition 4.6.}[CP] A semigroup $\mathbf{S}$ is \emph{completely}
\emph{simple} if and only if there exists no proper two-sided
ideal of $ \mathbf{S}$ and there exist no distinct idempotents $e$
and $f$ of $\mathbf{S}$ with $ef=fe=e$.


\vspace {.1 in}

While this is the standard definition we use an equivalent (see
Rees Theorem -- Theorem 1.3.2 in [H] or Theorem 3.5 in [CP]), more
combinatorial description which will allow us to parallel the
techniques in Section 3. Let $B$ and $C$ be sets,
$\mathbf{H}=(H,\cdot,e)$ be a group with identity $e$ and let
$P=\{p_{c,b}\}_{c\in C,b\in B}$ be a $|C|\times |B|$ matrix with
entries from $H$. Then $\mathcal{R}(B,\mathbf{H},C;P)$ is a
semigroup $(B\times H\times C,\odot )$ where
$$(b,h,c)\odot (b',h',c')=(b,hp_{c,b'}h',c')$$
(here the product $hp_{c,b'}h'$ is considered in the group
$\mathbf{H}$). It is well-known that
$\mathcal{R}(B,\mathbf{H},C;P)$ is a semigroup. Rees' Theorem says
that a semigroup $\mathbf{S}$ is completely simple if and only if
it is isomorphic to $\mathcal{R}(B,\mathbf{H},C;P)$ for some sets
$B$ and $C$, a group $\mathbf{H}$ and a $|C|\times |B|$ matrix $P$
with entries from $\mathbf{H}$.

Note that a semigroup $\mathbf{S}$ is a rectangular group,
discussed in the previous section, if and only if $\mathbf{S}$ is
isomorphic to $\mathcal{R}(B,\mathbf{H},C;P)$ where $p_{b,c}=e$
for all $b\in B$ and $c\in C$. One can easily verify that if $B$
or $C$ is a singleton set then $\mathcal{R}(B,\mathbf{H},C;P)$ is
a rectangular group. This follows from Proposition 4.7.
Consequently in view of Theorem 4 we can restrict ourselves to
the case when both $B$ and $C$ have cardinality at least $2$.
We recall the important properties of matrix representations.

\paragraph{Proposition 4.7.}[CP] Let sets $B$, $C$ and $b_0\in B$,
$c_0\in C$ be given. Let $\mathbf H$ be a group and $P$ be a
$|C|\times|B|$-matrix over $\mathbf H$. Then there exists a
$|C|\times|B|$-matrix $P'$ over $\mathbf H$ such that
\begin{itemize}
\item[(i)] $p'_{c,b_0}=p'_{c_0,b}=e$ for all $b\in B$ and $c\in
C$; \item[(ii)] the semigroups $\mathcal{R}(B,\mathbf{H},C;P)$,
and $\mathcal{R}(B,\mathbf{H} ,C;P')$ are isomorphic. $\Box$
\end{itemize}
\vspace {.1 in}

We say that a $|C|\times |B|$ matrix $P$ over a group $\mathbf{H}$
is $(c_0,b_0)$-\emph{standardized} for $ b_0\in B$ and $c_0\in C$
if $p_{c,b_0}=p_{c_0,b}=e$ for all $ b\in B$ and $c\in C$.

We say that a monoid $\mathbf{M}$ is \emph{completely}
\emph{simple} if $\mathbf{M}$ is isomorphic to $\mathbf{S}^1$ for
a completely simple semigroup $ \mathbf{S}$. Let $\mathcal{CS}$
denote the class of all finite, completely simple monoids.

In what follows we assume that finite, non-empty sets $B$ and $C$,
elements $b_0\in B$, $c_0\in C$, a finite group $\mathbf{H}$ and a
$(c_0,b_0)$-standardized $|C|\times |B|$ matrix $P$ over
$\mathbf{H}$ are given. Let $\mathbf{M}=(X,\cdot
,1)=\mathcal{R}(B,\mathbf{H},C;P)^1$ be a completely simple monoid
such that $X=\{B\times H\times C\}\cup \{1\}$ and $|X|=m=|B||H||C|+1$.
First we give a folklore statement regarding generators of
$\mathbf{M}$ (generalizing Lemma 4.3).

\paragraph{Lemma 4.8.} A set $U\subseteq B\times H\times C$ is a set
of generators of $\mathbf{M}$ whenever there exists a set $A$ of
generators of $\mathbf{H}$ such that \begin{enumerate} \item for
every $b\in B$ there exist $h\in H$ and $c\in C$ with $(b,h,c )\in
U$; \item for every $c\in C$ there exist $h\in H$ and $b\in B$
with $(b,h,c )\in U$; \item for every $a\in A$ there exist $b\in
B$ and $c\in C$ with $(b,a,c )\in U$. $\Box$
\end{enumerate}

\vspace {.1 in}

Let $U\subseteq A\times H\times B$ be a set of generators and let
$\phi :\binom {[t]}{2}\rightarrow\mathfrak{P}(U)$ be a mapping
with $(i,j)\mapsto B_{ij}$. Instead of using condition
$(\mathbf{P})$, we will use Lemma 4.9 which gives three conditions
on $\phi$ that imply $(\mathbf{P})$. Then, for a suitable $t$, we
construct $\phi$ satisfying these conditions. The construction
then yields an upper estimate on $t$.

\paragraph{Lemma 4.9.} Suppose the family $\{B_{ij}\mid (i,j)\in {[t] \choose 2}\}$
satisfies: \begin{itemize}  \item[(h1)] For every $c,c'\in C$ with
$c\ne c'$ there exists $(i,j)\in\binom { [t]}2$ such that $U\cap
(B\times H\times \{c\})\subseteq B_{ij}$ and $B_{ij}\cap(B \times
H\times \{c'\})=\emptyset$. \item[(h2)] For every $(b,h,c)\in U$
and every $(b',h')\in B\times H$ with $( b,h)\ne (b',h')$ there
exists $(i,j)\in\binom {[t]}2$ such that $(b,h,c)\in B_{ij}$ and $
(b',h',c)\notin B_{ij}$. \item[(h3)] For every $(b,h,c)\in U$,
every $c'\in C$ and every $h'\in H$ with $p_{c',b}h\ne h'$ there
exists $(i,j)\in\binom {[t]}2$ such that $ (b,h,c)\in B_{ij}$ and
if $(\bar {b},\bar {h},c)\in B_{ij}$ then $p_{c',\bar {b}}\bar {h}
\ne h'$.
\end{itemize}
Then $\phi$ satisfies condition $(\mathbf{P})$ and, thus,
$\End(F_{\mathcal {P}}*H)\cong \mathbf{M}$.

\paragraph{Proof:} Recall that we need to show for every pair $x_1,x_2\in X$
$$B(x_1,x_2)=\bigcup_{ij} \{B_{ij}\mid B_{ij}\cap
R(x_1,x_2)=\emptyset\}=U\setminus R(x_1,x_2).$$

As $B(x_1,x_2)\subseteq U\setminus R(x_1,x_2)$ is clear, we show
only the reverse inclusion. We consider several cases:

(a) If $x_2=1$ then $R(x_1,x_2)\cap U=\emptyset$. Consequently,
condition $(\mathbf{P})$ becomes $B(x_1,x_2)=U$. To show this
equality fix $(b,h,c)\in U$. By (h1) (applied with $c'$
arbitrary), there exists $(i,j)\in\binom { [t]}2$ such that $U\cap
(B\times H\times \{c\})\subseteq B_{ij}$ and thus $(b,h,c)\in
B_{ij}$. Since $B_{ij}\cap R(x_1,x_2)=\emptyset$, by assumption,
$(b,h,c)\in B(x_1,x_2)$. As $(b,h,c)$ was an arbitrary element
from $U$ we get $B(x_1,x_2)=U$.

(b) If $x_1=1$ then $R(x_1,x_2)=\{x_2\}$. Consequently, condition
$(\mathbf{P})$ becomes $B(x_1,x_2)=U\setminus \{x_2\}$. As above,
one containment is clear and we need to show only
$B(x_1,x_2)\supset U\setminus \{x_2\}$. To this end set
$x_2=(b_2,h_2,c_2)$, we are going to show that an arbitrary
$x=(b,h,c)\in U\setminus \{x_2\}$ belongs to $B(x_1,x_2)$. We
distinguish two subcases: namely, $c\neq c_2$ and $c=c_2$.

If $c\neq c_2$ then, by (h1), there exists $(i,j)\in\binom {
[t]}2$ such that $U\cap (B\times H\times \{c\})\subseteq B_{ij}$
and $B_{ij}\cap B \times H\times \{c_2\}=\emptyset$. Thus
$(b,h,c)\in B_{ij}$ and $B_{ij}\cap R(x_1,x_2)=\emptyset$. Hence,
$(b,h,c)\in B(x_1,x_2)$.

If $c=c_2$ then $(b,h)\ne(b_2,h_2)$ and so, by (h2), there exists
$(i,j)\in\binom {[t]}2$ such that $x_2\notin B_{i,j}$ and $(b,h,c)=(b,h,c_2)\in B_{ij}$.
Consequently, $R(x_1,x_2)\cap B_{ij}=\emptyset$ and $(b,h,c)\in
B(x_1,x_2)$, as required.

(c) The remaining case is $x_1=(b_1,h_1,c_1),~ x_2=(b_2,h_2,c_2)$.
Then

\begin{equation}
R(x_1,x_2)= \{(\bar{b},\bar{h},c_2)\mid \bar{b}\in B, \bar{h}\in
H, h_1p_{c_1,\bar{b}} \bar{h}=h_2\}.
\end{equation}

Again, we need to show $$U\setminus \{(\bar{b},\bar{h},c_2)\mid
\bar{b}\in B, \bar{h}\in H, h_2=h_1 p_{c_1,\bar{b}}\bar{h}
\}\subset B(x_1,x_2).$$

Assume, therefore, that $(b,h,c)\in U\setminus R(x_1,x_2)$. If
$c\ne c_2$ then, by (h1) (applied with $c'=c_2$), $(b,h,c)\in
B(x_1,x_2)$. Thus we can assume that $c=c_2$ which implies that
$h_2\neq h_1 p_{c_1,b}h$. Consequently $p_{c_1,b}h\neq
h_1^{-1}h_2$ and, by (h3) (applied with $h'=h_1^{-1}h_2$ and
$c'=c_1$), there exists $(i,j)\in\binom {[t]}2$ with $(b,h,c)\in
B_{ij}$ and if $(\bar{b},\bar{h},c)\in B_{ij}$ then
$p_{c_1,\bar{b}}\bar{h}\neq h_1^{-1}h_2$ (i.e.
$h_1p_{c_1,\bar{b}}\bar{h}\neq h_2$). Since we have just
established that $(b,h,c)\in B_{ij}$ it remains to show that
$B_{ij}\cap R(x_1,x_2)=\emptyset$. To this end let
$(\bar{b},\bar{h},\bar{c})\in B_{ij}$. If $\bar{c}\neq c_2$ then,
by (3), $(\bar{b},\bar{h},\bar{c})\notin R(x_1,x_2)$. If
$\bar{c}=c_2(=c)$ then $h_1p_{c_1,\bar{b}}\bar{h}\neq h_2$ and, by
(3), $(\bar{b},\bar{h},\bar{c})\notin R(x_1,x_2)$ as well. In
either case $B_{ij}\cap R(x_1,x_2)=\emptyset$ follows.
Consequently, $B(x_1,x_2)=U\setminus R(x_1,x_2)$, completing the
proof. $\Box$

\vspace {.1 in}

Observe that for $i=1,2,3$ if a family $\mathcal{F}_i$ satisfies
condition (hi) then the family $\mathcal{F}=\mathcal{F}_1\cup
\mathcal{F}_2\cup \mathcal{F}_3$ satisfies (h1), (h2) and (h3). In
Lemma 4.10 we will construct families satisfying (h1) and (h2).

\paragraph{Lemma 4.10.} For every set $U\subseteq B\times H\times C$
of generators of $\mathbf{M}$ there exist a family
$\mathcal{F}_1=\{Y_i\mid i\in I_1\}$ of subsets of $ U$ satisfying
(h1) with $|I_1|=2\lceil\log|C|\rceil$ and a family
$\mathcal{F}_2=\{ X_i\mid i\in I_2\}$ of subsets of $U$ satisfying
(h2) with $|I_2|=2\lceil\log|B\times H| \rceil$.


\paragraph{Proof:} Let $U\subseteq B\times H\times C$ be a set of
generators.  By Proposition 4.1, there exists \begin{itemize}
\item a family $\{T_i\mid i\in I_1\}$ of subsets of $C$ such that
$|I_1 |=2\lceil\log|C|\rceil$ and $~~~\{c\}=\bigcap \{T_i\mid i\in
I_1,\,c\in T_i\}$ for all $c\in C$. \item a family $\{W_i\mid i\in
I_2\}$ of subsets of $B\times H$ such that
$|I_2|=\lceil\log|B\times H|\rceil$ $~~$ and $\{y\}=\bigcap
\{W_i\mid i\in I_2,\,y\in W_i\}$ for all $y\in B\times H$.
\end{itemize}

Define $Y_i=\{(b,h,c)\in U\mid c\in T_i\}$ for all $i\in I_1$,
$X_i=\{(b,h,c)\in U\mid (b,h)\in W_i\}$ for all $i\in I_2$ and
consider the families $\mathcal{F}_1=\{Y_i\mid i\in I_1\}$ and
$\mathcal{F}_2=\{X_i\mid i\in I_2\}$. If $c_1$ and $c_2$ are
distinct elements of $C$ then there exists $i\in I_1$ with $c_1\in
T_i$ and $c_2\notin T_i$. Hence $U\cap (B\times H\times
\{c_1\})\subseteq Y_i$ and $(B\times H\times \{c_2\})\cap
Y_i=\emptyset$. Thus $\mathcal{F}_1$ satisfies (h1). If
$(b,h,c)\in U$ and $(b',h')\in B\times H$ with $ (b,h)\ne (b',h')$
then there exists $i\in I_2$ with $(b,h)\in W_i$ and
$(b',h')\notin W_i$. Then $(b,h,c)\in \{(b,h)\}\times C\subseteq
X_i$ and $(\{(b',h')\}\times C)\cap X_i=\emptyset$, thus
$(b',h',c)\notin X_i$. Whence $\mathcal{F}_2$ satisfies (h2).
$\Box$

\vspace {.1 in}

Next we give two constructions for a family satisfying condition
(h3). Then, depending on the size of $C$, we choose the smaller
family $\mathcal{F}_3$ and show that it has size $O(m^{\frac 13})$
yielding $|G(\mathbf{M},\phi)|=O(m^{\frac 76})$.


\paragraph{Lemma 4.11.} For every set $U\subseteq B\times H\times C$
of generators of $ \mathbf{M}$ there exists a family
$\mathcal{F}_3$ of subsets of $U$ satisfying (h3) of size
$2|C|\lceil\log|H|\rceil$.

\paragraph{Proof:} By Lemma 4.1, there exists a family $\{H_i\mid i\in I_
3\}$ of subsets of $H$ such that $\{h\}=\bigcap \{H_i\mid i\in
I_3,\,h\in H_i\}$ for all $h\in H$ and
$|I_3|=2\lceil\log(|H|)\rceil$. For every $c\in C$ and $i\in I_3$
define a set $D_{i,c}=\{(\bar{b},\bar{h},\bar{c})\in U\mid
p_{c,\bar{b}}\bar{h}\in H_i\}$. Let $(b,h,c)\in U$, $c'\in C$ and
$h'\in H$ with $p_{c',b}h\ne h'$ be given. Then there exists $i\in
I_3$ with $p_{c',b}h\in H_i$ and $h'\notin H_i$. We prove that
$(b,h,c)\in D_{i,c'}$ and if $(\bar{b},\bar{h},\bar{c})\in
D_{i,c'}$ then $p_{c',\bar{b}}\bar{h}\ne h'$. Thus $D_{i,c'}$
satisfies the statement stronger than condition (h3) for given
$(b,h,c)$, $c'$ and $h'$. Since $p_{c',b}h\in H_i$ we conclude
that $(b,h,c)\in D_{i,c'}$. If $(\bar{b},\bar{h},\bar{c})\in
D_{i,c'}$ then $p_{c',\bar{b}}\bar{h}\in H_i$. On the other hand,
$h'\notin H_i$ and we infer that $p_{c',\bar{b}}\bar{h}\ne h'$.
Whence the family $\{D_{i,c}\mid i\in I_3,\,c\in C\}$ satisfies
condition (h3). $\Box$


\paragraph{Lemma 4.12.} There exists a set $U\subseteq B\times
H\times C$ of generators of $\mathbf{M}$ and a family
$\mathcal{F}_3$ of subsets of $U$ satisfying (h3) of size
$\left\lceil\frac {|B|}{|C|}\right\rceil +2\lceil\log\log|H
|\rceil$.


\paragraph{Proof:} First we construct a set $U\subseteq B\times H\times
C$ of generators. Clearly, there exists a family $\{B_i\mid i\in
I_3\}$ of subsets of $B$ such that $B=\bigcup_{i\in I_3}B_i$,
$I_3=\left\lceil\frac{|B|}{|C|}\right\rceil$ and $ |B_i|\le |C|$
for all $i\in I_3$. For every $i\in I_3$ choose a surjective
mapping $\psi_i:C\rightarrow B_i$. Let $A$ be a set of generators
of $\mathbf{H}$ with $|A|\le\log|H|$ and $e\notin A$ ($e$ is the
unity of $\mathbf{H}$). Then $U=\{(\psi_i(c),e,c)\mid c\in
C,\,i\in I_3\}\cup \{(b_0,a,c_0)\mid a\in A\}$. By Lemma 4.8,
since $B=\bigcup \{\textrm{Im}(\psi_i)\mid i\in I_3\}$, $U$ is a
set of generators. Next we shall construct a family of subsets of
$U$. By Proposition 4.1, there exists a family $\{A_i\mid i\in
I_4\}$ of subsets of $ A$ such that $\{a\}=\bigcap \{A_i\mid i\in
I_4,\,a\in A_i\}$ for all $a\in A$ and
$|I_4|=2\lceil\log|A|\rceil\le 2\lceil\log\log|H|\rceil$. Without
loss of generality we can assume that $I_3\cap I_4=\emptyset$. Now
define \begin{itemize} \item $D_i=\{(\psi_i(c),e,c)\mid c\in C\}$
for $i\in I_3$, \item $D_i=\{(b_0,a,c_0)\mid a\in A_i\}$ for $i\in
I_4$, \item $\mathcal{F}_3=\{D_i \mid i\in I_3\cup I_4\}.$
\end{itemize}



Since $|I_3\cup I_4|\le\left\lceil\frac {|B|}{ |C|}\right\rceil
+2\lceil\log\log|H|\rceil$ it suffices to prove that condition
(h3) is satisfied. For this purpose assume that $(b,h,c)\in U$,
$c'\in C$ and $h'\in H$ with $p_{c',b} h\ne h'$ are given. First
assume that $h=e$. Then, $h\notin A$, there exists $i\in I_3$ with
$b=\psi_i(c)$. Clearly, then $(b,h,c)\in D_i$ and if $(\bar
{b},\bar {h},c)\in D_i$ then $(\bar {b},\bar {h},c)=(b,h,c )$.
Thus $(\bar {b},\bar {h},c)\in D_i$ implies $p_{c',\bar {b}}\bar
{h}\ne h'$ and thus in this case condition (h3) is satisfied.
Secondly, if $h\ne e$ then $h\in A$, $ b=b_0$ and $c=c_0$ and
there exists $i\in I_4$ with $h\in A_i$ and $h'\notin A_i$. Hence
$ (b,h,c)\in D_i$ and if $(\bar {b},\bar {h},\bar {c})\in D_i$
then $\bar {b}=b_0$, $\bar { c}=c_0$ and $\bar {h}\in A_i$. Since
$P$ is $(c_0,b_0)$-standardized $p_{c',\bar {b}}=e$ and
consequently $p_{c',\bar {b}}\bar {h}=\bar {h}$. On the other
hand, as $\bar {h}\in A_i$ and $h'\notin A_i$, we have $p_{c',\bar
{b}}\bar {h}=\bar {h}\neq h'$. Thus (h3) is satisfied. $\Box$

\vspace {.1 in}

We recall that $\mathcal{CS}$ is the class of all monoids
$\mathbf{M} =\mathbf{S}^1$ where $\mathbf{S}$ is a finite,
completely simple semigroup.


\paragraph{Theorem 6.}For all $m,~\nu_{\mathcal{C}\mathcal{S}}(m)\leq (2+o(1))m^{\frac
{7}{6}}$.
\paragraph{Proof:} We need to show that $\nu_{\mathcal{CS}}(m)\leq (
2+o(1))m^{\frac 76}$. Let $\mathbf{M}=(X,\cdot ,1)$ be a
completely simple monoid isomorphic to
$\mathcal{R}(B,\mathbf{H},C;P)^1$ for some finite non-empty sets
$B$ and $C$, a finite group $\mathbf{H}$ and a $|C|\times |B|$
matrix $P$ over $\mathbf{H}$. Let $|X|=m$. If $|C|\le\frac
{m^{\frac 13}}{\lceil\log|H|\rceil}$ then we can apply Lemmas 4.10
and 4.11 to a set $U\subseteq B\times H\times C$ of generators of
$\mathbf{M}$ yielding a family $\mathcal{F}=\mathcal{F}_1\cup
\mathcal{F}_2\cup \mathcal{F}_3$ of subsets of $U$ satisfying
conditions (h1), (h2) and (h3) with
\begin{align*}|\mathcal{F}| &\leq 2\lceil\log| C|\rceil +
2\lceil\log|B\times H|\rceil + \left\lceil\frac {m^{\frac
13}}{\lceil\log|H|\rceil}2\lceil\log
|H|\rceil\right\rceil \\
 &\leq 2\left( \lceil m^{\frac 13}\rceil
+\lceil\log|B\times H\times C|\rceil+1\right)\\
&=(2+o(1))m^{\frac 13}.
\end{align*}

If $|C|\ge\frac {m^{\frac 13}}{\lceil\log|H|\rceil}$ then we can
apply Lemmas 4.10 and 4.12 to obtain a set $U\subseteq B\times
H\times C$ of generators of $\mathbf{M}$ and a family
$\mathcal{F}=\mathcal{F}_1\cup \mathcal{F}_2\cup \mathcal{F}_3$ of
subsets of $U$ satisfying conditions (h1), (h2) and (h3). First we
bound the size of $\mathcal{F}_3$. Indeed, by Lemma 4.12


\begin{align*}|\mathcal{F}_3| &= \left\lceil\frac {|B|}{|C|}\right\rceil
+2\lceil\log\log|H |\rceil =\left\lceil\frac
{|B||C||H|}{|C|^2|H|}\right\rceil +2\lceil\log\log|H |\rceil \\
&\leq \frac{m\log^2|H|}{m^{\frac 23}|H|}(1+o(1))= \frac{m^{\frac
13}\log^2|H|}{|H|}(1+o(1)) \\
&\leq 1.2 m^{\frac 13}(1+o(1))
\end{align*}
where the last inequality holds since $\frac{\log^2 x}{x}\leq 1.2$
for all $x\in\mathbb{N}$.

By Lemma 4.10 we have
$$|\mathcal{F}_1\cup\mathcal{F}_2|\leq 2\lceil\log|B\times H|\rceil
+2\lceil\log|C|\rceil\leq o(m^{\frac 13})$$ and consequently
$|\mathcal{F}|\leq (2+o(1)) m^{\frac 13}$.

Finally, since $t$ is the smallest natural number such that
$\binom t2\ge |\mathcal{F}|$ we get, in either of the above cases,
that $t=(2+o(1))m^{\frac 16}$ and, using Lemma 4.9, we conclude
that $\nu_{\mathcal{CS}}(m)=(2+o(1))m^{\frac 76}$. $\Box$

















