\mychapter{Construction}


\section {A Reduction to $\mathcal{P}$-graphs}
%\end{section }

Before giving the details of our construction we introduce the
notions of $\mathcal{P}$-graph and $\mathcal{P}$-endomorphism. We
will prove that the problem of representing a monoid as the
endomorphism monoid of a graph can be reduced to the problem of
representation by a $\mathcal{P}$-endomorphism monoid of a
$\mathcal{P}$-graph.

\paragraph{Definition.} A \emph{partition} \emph{graph} (shortly a
$\mathcal{P}$-\emph{graph}) is a graph $F_{\mathcal{P}}$ where $F$
is an undirected graph equipped with a partition (coloring)
$\mathcal{P}$ of the vertex set $V(F)=\cup_{i=0}^{t}V_i$ where
each $V_i$ is an independent set in $F$.

\paragraph{Definition.} A $\mathcal{P}$-\emph{endomorphism} of $F_{\mathcal{P}}$ is a graph
homomorphism of $F$ such that $f(V_i)\subseteq V_i$ for all $i\in
[0,t]$.

\vspace{.1 in}

By $\End_{\mathcal{P}}(F_{\mathcal{P}})$ we denote the set of all
$\mathcal{P}$-endomorphisms. Then
$\End_{\mathcal{P}}(F_{\mathcal{P}})$ contains the identity map on
$V(F)$ and is closed under composition of mappings. Thus,
$\End_{\mathcal{P}}(F_{\mathcal{P}})$ is a transformation monoid.

Our construction has three parts: a $\mathcal{P}$-graph
$F_\mathcal{P}$ (to be defined in Section 3.3), a rigid graph $H$ (that is a graph with no non-trivial endomorphisms)
and an amalgamation $\ast $ of the two.

\paragraph{The Rigid Graph.}Similar graphs were considered in [HN].
We present a somewhat simplified version from [PT]. For every
$q\geq 3$ there exists a rigid graph $H=H_q$ on $4q+1$ vertices
and less than $4q^2$ edges such that every $z\in V(H)$ is contained
in a clique of size $q$. Formally, we set
\begin{itemize}
\item $V(H)=\{0,1,\dots,4q\}$
\item $E(H)=\{\{z,z'\}\mid z,z'\in Z,\,|z-z'|<q\}\cup \{\{0,4q\},\{0,3q-1\}\}.$
\end{itemize}

From [PT] we know that $H$ is rigid and, clearly, every
vertex $z\in V(H)$ belongs to a clique of size $q$. Moreover, no $x\in\{3q,3q+1,\dots,4q-2\}$ is adjacent to $0$ or $2q-1$ and there exists no joint neighbor of $0$ and $2q-1$. These facts are exploited in the following construction.

\paragraph{The Amalgamation.} Let $F_{\mathcal{P}}$ be a $\mathcal{P}$-graph
with $V(F)=\cup_{i=0}^{t}V_i$ and suppose that for every $i=1,2,\dots,t$ each $v\in V_i$
has a neighbor from $V_0$ and every $v\in V_0$ has at most one neighbor from $V_i$
for all $i=1,2,\dots,t$. We set
$q=t+2$ and let $H=H_q$ be the rigid graph defined above. We
define the graph $G=F_{\mathcal{P}}\ast H$ (see Figure 3.2) as follows: set
$V(G)=V(F)\cup V(H)$ and $E(G)=E(F)\cup E(H)\cup L$
where
$$L=\bigcup_{i=1}^t\{\{3q-1+i,v\}\mid  v\in V_i\}\cup\{\{0,v\},\{2q-1,v\}\mid v\in V_0\}.$$

\vspace{.1 in}

The next theorem reduces a representation problem of monoids by
endomorphism monoids of graphs to a representation of monoids by
$\mathcal{P}$-endomor\-phism monoids.

\paragraph{Proposition 3.1.}Let $G=F_{\mathcal{P}}\ast H$ be the graph described above. Then
$\End_{\mathcal{P}}(F_{\mathcal{P}})\cong\End{G}$.

\paragraph{Proof:} We show that $g:V(G)\rightarrow V(G)$ is an endomorphism of
$G$ if and only if $g$ is the identity on $H$ and restricts to a
$\mathcal{P}$-endomorphism of $F_{\mathcal{P}}$. Consider a
$\mathcal{P}$-endomorphism $f:V(F)\rightarrow V(F)$ of
$F_{\mathcal{P}}$. Define $g:V(G)\rightarrow V(G)$ by

\begin{displaymath}g(w)=\left\{\begin{array}{ll}f(w) & \text{if}~w\in V\\
w & \text{if}~w\notin V.\end{array}\right.\end{displaymath}Then
$g$ preserves $E(F)$ and $E(H)$ and, as $f(V_i)\subseteq V_i$ for
all $i\in [0,t]$, $g$ preserves $L$ as well. Hence, $g$ is an
endomorphism of $G$.

Conversely, let $g$ be an endomorphism of $G$ and pick $z\in
V(H)$. Since every vertex $z\in V(H)$ belongs to a clique of $G$
of size $q=t+2$ and every clique of $G$ containing $v\in V(F)$ has
size at most $t+1$ we have $g(z)\in V(H)$. Since $H$ is rigid we
infer that $g(z)=z$ for all $z\in V(H)$. Next we prove that
$g(V_0)\subseteq V_0$.
Let $v\in V_0$, then $\{0,v\}$ and $\{2q-1,v\}$ are edges of $G$.
On the other hand, the neighborhoods of $0$ and $2q-1$ are disjoint
in $H$. Hence $g(v)\notin\{0,1,\dots,4q\}$.
Since $\{0,v\}\in E(G)$ and $g(0)=0$ but $\{0,y\}\in E(G)$ for no
$i\in I\setminus \{0\}$ and $y\in V_i$ we infer that $g(V_0)\subseteq V_0$.
Finally, we prove that $g(V_i)\subseteq V_i$ for all $i\in I$. Consider
$i\in I\setminus \{0\}$ then for every $y\in V_i$ there exists $x\in V_0$
with $\{x,y\}\in E(G)$. Then $\{g(x),g(y)\}\in E(G)$ and hence $y\in V(F_{\mathcal{P}})\cup\{0,2q-1\}$. Further $\{3q-1+i,v\}\in E(G)$ which
implies $\{3q-1+i,g(v)\}\in E(G)$. Since $\{0,3q-1+i\},\{2q-1,3q-1+i\}\notin E(G)$
and since $z\in V(F_{\mathcal{P}})$ is a neighbor of $3q-1+i$ exactly when
$z\in V_i$ we conclude that $g(v)\in V_i$ (see Figure 3.1). Thus $g(V_i)\subseteq V_i$ for
all $i\in I$. Since $g$ is an endomorphism of $G$ we infer that
$\{g(x),g(y)\}\in E(F_{\mathcal{P}})$ for all $\{x,y\}\in E(F_{\mathcal{P}})$,
and therefore, the restriction of $g$ to $V(F_{\mathcal{P}})$ is a
$\mathcal{P}$-endomorphism of $F_{\mathcal{P}}$, as required.
$\Box$


\begin{figure}
 \centering
 \epsfxsize=5 in
 \epsfysize=3 in
  \epsfbox{the-1.eps}
 \caption {Amalgamation}
\end{figure}

\section {Translations of Monoids}
%\end{section}

Before giving the remaining details of our construction we discuss
the set of left (right) translations of a monoid, a notion upon
which almost all representations of a monoid as an endomorphism
monoid are based.

Let $\mathbf{M}=(X,\cdot,1 )$ be a monoid and $x\in X$. Then a
mapping $l:X\rightarrow X$ is called a \emph{left}
\emph{translation} by $x$ if $l(y)=xy$ for all $y\in X$. By
$\mathbf{M}^L$ we denote the set of all left translations of
$\mathbf{M}$ under composition. Analogously, a right translation
$r\in\mathbf{M}^R$ is a mapping given by $y\mapsto yx$. The
following statement was originally formulated for semigroups. We
adjust it to our purposes as follows.

\paragraph{Lemma 3.2.}[CP] Let $\mathbf{M}=(X,\cdot,1)$ and $\mathbf{M}'=(X,\odot,1)$ be
monoids where $x\odot y=y\cdot x$ for all $x,y\in X$. Then
$\mathbf{M}^L\cong\mathbf{M}$ and
$\mathbf{M}^R\cong\mathbf{M}'$. $\Box$

\vspace{.1 in}

The following characterization will be useful to us.

\paragraph{Lemma 3.3.}[GH] Let $\mathbf{M}=(X,\cdot ,1)$ be a monoid.
A mapping $g:X\rightarrow X$ is a left (or right)
translation by some $x\in X$ if and only if $g\circ r=r\circ g$
for each right (or left) translation $r\in\mathbf{M}^R$ (or $r\in\mathbf{M}^L$, resp.).
$\Box$

\vspace{.1 in}

These statements provide a basis for identifying and realizing
monoids.





\section {The graph $F_{\mathcal{P}}$}
%\end{section}
We fix the following notation for Chapters 3 and 4. Fix a
natural number $t>1$ and let ${[t]\choose 2}=\{(i,j)\mid 1\leq
i<j\leq t\}$. For a given set $A$ let $\mathfrak {P}(A)=\{B\mid
B\subseteq A\}$. Fix a monoid $\mathbf{M}=(X,\cdot ,1)$ where
$|X|=m$, a set of generators $A$ and a map $\phi :{[t]\choose
2}\rightarrow\mathfrak {P}(A)$ via $(i,j)\mapsto B_{ij}$. We
define a $\mathcal {P}$-graph
$F_{\mathcal{P}}=F_{\mathcal{P}}(\mathbf{M},\phi)$ as follows:


\begin{itemize} \item $V(F)=\bigcup_{i=0}^{t}V_i$ where
$V_i=X\times \{i\}$;\item $\mathcal{P}=\{V_i\mid i\in [0,t]\}$;
\item $E_0=\{\{(x,0),(x,i)\}\mid x\in X,i\in[1,t]\}$; \item
$E_{ij}=\{\{(x,i),(xa,j)\}\mid x\in X,a\in B_{ij}\}$ for all
$(i,j)\in {[t]\choose 2}$; \item $E=E_0\cup (\bigcup \{E_{ij}\mid
(i,j)\in {[t]\choose 2}\})$.\end{itemize} \vspace{.1 in}

Furthermore, let $R(x,x')=\{a\in X\mid xa=x'\}$ and set
$B(x,x')=\bigcup_{ij} \{B_{ij}\mid B_{ij}\cap
R(x,x')=\emptyset\}$. Finally, suppose $\phi$ satisfies the
following:


\begin{figure}
 \centering
 \epsfxsize=4 in
 \epsfysize=3 in
  \epsfbox{benji.eps}
 \caption {$G=F_{\mathcal{P}}\ast H$}
\end{figure}



\paragraph{Condition (P).} $B(x,x')=A\setminus R(x,x')$ for
every $x,x'\in X$.

\vspace{.1in}

\paragraph{Remark 1.}Note that the graph $F_{\mathcal{P}}=G(\mathbf{M},\phi)$
satisfies the two requirements made in the previous
section:\newline (i) all sets $V_i$ are independent;\newline (ii)
the edges between $V_0$ and $V_i$ form a perfect matching for all
$i\in[1,t]$.

\paragraph{Remark 2.} By definition $B(x,x')\subseteq A\setminus R(x,x')$.
Therefore, in order to verify condition $(\mathbf{P})$, it will be
sufficient to prove the opposite inclusion.


\paragraph{Remark 3.} Note that $(\mathbf{P})$ implies $$\bigcup_{ij}B_{ij}=A.$$
If $|X|=1$ this is trivial. Otherwise, for every $a\in A$ we have
$a\notin R(1,a')$ for any $a'\neq a$. Hence, by $(\mathbf{P})$ we
get that $a\in B(1,a')$ and thus $a\in B_{ij}$ for some $(i,j)\in
{[t]\choose 2}$. If
$$\bigcup_{ij}B_{ij}=A\quad\text{and}\quad |B_{ij}|\leq1\quad\text{for all }(i,j)\in\binom{[t]}2$$
then $(\mathbf{P})$ is true. Hence, if $t\geq\sqrt{2|A|}$
then we can satisfy $(\mathbf{P})$ because ${t\choose 2}\geq |A|$.
\vspace {.1 in}

With the above construction we are able to state our central
technical result.

\paragraph{Proposition 3.4.} Let $F_{\mathcal{P}}$
be the graph defined above. Then the graph
$G=G(\mathbf{M},\phi)=F_{\mathcal{P}}\ast H$ introduced in
Proposition 3.1 (see Figure 3.2) has the following properties:

\begin{itemize} \item[(i)] $|V(G)|=(t+1)m+4t+9<(t+1)(m+4)+5$,
\item[(ii)]
\begin{align*}|E(G)|=&|E(F)|+|V(F)|+|V_0|+|E(H)|\leq\\&\left(\sum_{(i,j)\in\binom{[t]}2}|B_{ij}|
\right)m+2mt+2m+4(t+2)^2,\end{align*}
\item[(iii)]if $(\mathbf P)$ holds then $\End(G)\cong\mathbf{M}$.
\end{itemize}

\paragraph{Proof:}Since properties (i) and (ii) immediately follow
from the construction (because $|E_{ij}|=|B_{ij}|m$ for all $(i,j)\in\binom{[t]}2$, and $|E_0|=|\bigcup_{i=1}^tV_i|=tm$) we will verify (iii) only. By Proposition
3.1, $\End (G)\cong\End_{\mathcal{P}}(F_{\mathcal{P}})$ and, to
establish the isomorphism, it remains only to prove that
$\End_{\mathcal{P}}(F_{\mathcal{P}})\cong\mathbf{M}$.

\paragraph{Lemma 3.5.}$\End_{\mathcal{P}}(F_{\mathcal{P}})\cong\mathbf{M}$.
\vspace {.1 in}

We introduce the following notation. Let
$f\in\End_{\mathcal{P}}(F_{\mathcal{P}})$. Then $f(V_i)\subseteq
V_i$ for $i\in [0,t]$ and consequently $f(x,i)=(x',i)$ for some
$x'\in X$. For each $f\in\End_{\mathcal{P}}(F_{\mathcal{P}})$ let
$\{f^i\}_{i=0}^{t}$ be the class of maps where $f^i:X\rightarrow
X$ via $x\mapsto x'$.


\paragraph{Fact.}For each $f\in\End_{\mathcal{P}}(F_{\mathcal{P}})$ and
for all $0\leq i,j\leq t,~f^i=f^j$ holds.
\paragraph{Proof of Fact:}Fix $x\in X$, $f\in\End_{\mathcal{P}}(F_{\mathcal{P}})$
and $i\in [1,t]$. It suffices to show that $f^i=f^0$. From
$f(V_0)\subseteq V_0$ it follows $f(v)\in V_0$ for all $v\in V_0$.
Thus $\{f(v),f(w)\}\in E_0$ for all $\{v,w\}\in E_0$. As
$\{v,w\}\in E_0$ if and only if $v=(x,0)$ and $w=(x,i)$ for some
$x\in X$ and $i\in[1,t]$, we conclude that
$\{(f^0(x),0),(f^i(x),i)\}\in E_0$ for all $x\in X$ and $i\in
[1,t]$ and hence, $f^0(x)=f^i(x)$ for all $x\in X$ and
$i\in[1,t]$. $\Box$ \vspace{.1 in}

Since $f^i$ depends only on $f$ (and, in particular, is
independent of $i$) there is a well defined map on $X$ given by
$\tilde{f}=f^i,~i\in [0,t]$. Let $\mathcal{D}=\{\tilde{f}\mid
f\in\End_{\mathcal{P}}(F_{\mathcal{P}})\}$. Since $\mathcal{D}$ is
closed under composition and contains the identity mapping it is a
transformation monoid. We shall sometimes refer to elements of
$\mathcal{D}$ as \emph{determining mappings}.

\paragraph{Proof of Lemma 3.5:} By Lemma 3.2 it suffices to show that
$\End_{\mathcal{P}}(F_{\mathcal{P}})\cong\mathbf{M}^L$. We do this
in two stages -- first showing
$\End_{\mathcal{P}}(F_{\mathcal{P}})\cong\mathcal{D}$ and then
showing $\mathcal{D}\cong\mathbf{M}^L$.

\paragraph{Claim 3.51.} The map
$\psi:\End_{\mathcal{P}}(F_{\mathcal{P}})\rightarrow\mathcal{D}$
sending $f\mapsto \tilde{f}$ is an isomorphism.
\paragraph{Proof:} The map is onto by definition. We need to show it is one-to-one
and respects composition. Let
$f,g\in\End_{\mathcal{P}}(F_{\mathcal{P}})$ be distinct and pick
$v\in V(F)$ such that $f(v)\neq g(v)$. There exists $x\in X$ and
$i\in 0\ldots t$ such that $v=(x,i)$. Thus, $(f^i(x),i)=f(x,i)\neq
g(x,i)=(g^i(x),i)$ and so $\tilde{f}(x)\neq \tilde{g}(x)$ and
consequently the map is one-to-one. Secondly, we have
$$(\tilde{f}\tilde{g}(x),i)=f(\tilde{g}(x),i)=f(g(x,i))=(f\circ
g)(x,i)=(\widetilde{fg}(x),i).$$ Thus,
$\widetilde{fg}=\tilde{f}\tilde{g}$ and
$\psi$ is an isomorphism. $\Box$

\paragraph{Claim 3.52.}$\mathcal{D}=\mathbf{M}^L$.
\paragraph{Proof:} We show both inclusions. To establish $\mathbf{M}^L\subseteq\mathcal{D}$
we first need to characterize the maps in $\mathcal{D}$.

\paragraph{Lemma 3.53.} Let $g:X\rightarrow X$.
Then $g\in\mathcal{D}$ if and only if for every $(i,j)\in
{[t]\choose 2}$, every $x\in X$ and every $a\in B_{ij}$ there
exists $b\in B_{ij}$ with $g(xa)=g(x)b$.

\paragraph{Proof:} Assume $g\in\mathcal{D}$. Then there exists
$f\in \End_{\mathcal{P}}(F_{\mathcal{P}})$ with $g=\tilde{f}$.
Choose $x\in X$, $(i,j)\in {[t]\choose 2}$ and $a\in B_{ij}$.
Since $\{(x,i),(xa,j)\}\in E_{ij}$ we get that
$\{f(x,i),f(xa,j)\}\in E_{ij}$ where $f(x,i)=(g(x),i)$ and
$f(xa,j)=(g(xa),j)$. Hence there exists $b\in B_{ij}$ with
$g(xa)=\tilde{f}(xa)=\tilde{f}(x)b=g(x)b$ and the condition is
satisfied.

Conversely, let $g:X\rightarrow X$ and assume that for every $x\in
X$, every $(i,j)\in {[t]\choose 2}$ and every $a\in B_{ij}$ there
exists $b\in B_{ij}$ with $g(xa)= g(x)b$. We define
$f:V(F)\rightarrow V(F)$ by $f(x,i)=(g(x),i)$ for all $x\in X$ and
all $i\in [0,t]$ and we show that $f$ is a $\mathcal
{P}$-endomorphism of $F_{\mathcal{P}}$. By the definition of $f$
we have $f(V_ i)\subseteq V_i$ for all $i\in [0,t]$ and
consequently $\{f(v),f(w)\}\in E_0$ for all $\{v,w\}\in E_0$. It
remains to prove that for every pair $(i,j), 1\leq i<j\leq t$ and
every $\{v,w\}\in E_{ij}$ we have $\{f(v),f(w)\}\in E_{ij}$.
Select $(i,j)\in {[t]\choose 2}$ and an edge $ \{v,w\}\in E_{ij}$.
There exists $x\in X$ and $a\in B_{ij}$ with $\{v,w\}=\{(x
,i),(xa,j)\}$. By assumption there exists $b\in B_{ij}$ with
$g(xa)=g(x)b$. From the definition of $f$ it follows that
$f(xa,j)=(g(xa),j)=(g(x)b,j)$ and, as $\{(g(x),i),(g(x)b,j)\}\in
E_{ij}$ we get that $\{f(x,i),f(xa,j)\}\in E_{ij}$, as required.
$\Box$

\paragraph{Proof of 3.52 (continued):} We first show $\mathbf{M}^L\subseteq\mathcal{D}$.
Let $r_a$ be a right translation by some $a\in A$.
If $g:X\longrightarrow X$ is a left translation of $\mathbf{M}$
then, by Lemma 3.3, for every $x\in X$ and $a\in A$ we have
$g(xa)=g\circ r_a(x)=r_a\circ g(x)=g(x)a$. Thus, $g$ satisfies the
conditions of Lemma 3.53 with $b=a$ and we get that
$\mathbf{M}^L\subseteq \mathcal{D}$. It remains to show the reverse inclusion $\mathcal{D}\subseteq\mathbf{M}^L$.
Let $g\in\mathcal{D}$ and $f\in
\End_{\mathcal{P}}(F_{\mathcal{P}})$ with $g=\tilde{f}$ and choose
$a\in A$. We prove that $g$ commutes with the right translation
$r_a$ of $a$. Indeed, if $g(x)a=r_a(g(x))\neq g(r_a(x))=g(xa)$,
then $a\notin R(g(x),g(xa))$ which implies, by
$(\mathbf{P})$, that $a\in B(g(x),g(xa))$. It follows that
there exists $(i,j)\in {[t]\choose 2}$ with $a\in B_{ij}$ and
$B_{ij}\cap R(g(x),g(xa))=\emptyset$. Thus, $\{(x,i),(xa,j)\}\in
E_{ij}$ while $\{f(x,i),f(xa,j)\}=\{(g(x),i),(g(xa),j)\}\notin
E_{ij}$ as $g(xa)\neq g(x)b$ for all $b\in B_{ij}$, contradicting
that $f$ is an endomorphism. Consequently $g$ commutes with $r_a$
and as $r_a$ was arbitrary (among right translations by
generators) we get that $g\in\mathbf{M}^L$, as desired. $\Box$
\medskip

This completes the proof of Lemma 3.5 and, hence the proof of
Proposition 3.4 as well. $\Box$ \vspace {.1 in}

Observe that the upper bounds in Theorems 1 and 2 follow:
\paragraph{Theorem 1 -- Upper Bound.} For all $m,~\varepsilon (m)\leq(1+o(1))m^2$.

\paragraph{Proof:} In order
to satisfy condition $(\mathbf P)$ it suffices, by Remark 3, to
set each $B_{ij}$ equal to a singleton such that  $$\bigcup_{(i,j)\in\binom{[t]}2}B_{ij}=A\quad\text{and}\quad\sum_{(i,j)\in\binom{[t]}2}|B_{ij}|\leq\binom t2.$$ By (iii) in
Proposition 3.4, $G(\mathbf M,\phi)\cong\mathbf M$. Hence, by (ii), we
have $|E(G)|\leq \binom t2m+2mt+2m+4(t+2)^2$ which, from
$t=\sqrt{2m}+1$ (see Remark 3) yields $|E(G)|\leq
m^2(1+o(1))$. $\Box$

\paragraph{Theorem 2 -- Upper Bound.}For all $m$ and $\alpha\in (0,\frac{1}{3}),~\nu(m,\alpha)\leq
(1+o(1))m^{\frac{2}{1+\alpha}}$
\paragraph{Proof:} For a given monoid $\mathbf{M}$
and $\alpha\in (0,\frac{1}{3})$ set
$t=(1+o(1))m^{\frac{1-\alpha}{1+\alpha}}$. Then ${t\choose 2}>m$
and hence, by Remark 3, condition $(\mathbf{P})$ is satisfied.
Thus, by Proposition 3.4, there exists a graph $G$ with
$|V(G)|=(t+1)(m+4)+5=(1+o(1))m^{\frac{2}{1+\alpha}}$ while
\begin{align*}
|E(G)|\leq& m^2+(2+o(1))m^{\frac{2}{1+\alpha}}+2m+(4+o(1))m^{\frac{2-2\alpha}{1+\alpha}}
=\\& m^2(1+o(1))=|V(G)|^{1+\alpha}\end{align*} as required. $\Box$

\vspace {.1 in}

Finally, we derive a bound for graphs with bounded average degree.

\vspace{.1 in}


\paragraph{Proposition 3.6.} For every monoid $\mathbf{M}=(X,\cdot,1)$ with $|X|=m$
there exists a graph $G$ such that $\End(G)\cong\mathbf{M}$,
$|E(G)|\leq (7+o(1))|V(G)|$ and $|V(G)|=m^2+5m+9$. Thus the average degree is less than $14$.

\paragraph{Proof:} If we set $t=m$ then, by Remark 3, we can satisfy $(\mathbf{P})$ and
$|V(G)|=m^2+5m+9$.
By Proposition 3.4, $|E(G)|\leq (m-1)m+2m^2+2m+4(m+2)^2=(7+o(1))m^2\leq (7+o(1))|V(G)|$. $\Box$


\section {Example}
%\end{section}

In this section we will construct a monoid $\mathbf{M}(n)$ of size
$m=2n+3$ such that every graph $G(\mathbf{M}(n),\phi)$ with
$\End(G(\mathbf{M}(n),\phi))\cong \mathbf{M}(n)$ satisfies $\binom
t2\geq n$. Consequently every such graph has $\Theta(n^{\frac
32})$ vertices.

Let $X=\{x_1,x_2,\dots,x_n\}$ and $Y=\{y_1,y_2,\dots,y_n\}$ be
disjoint $n$-element sets. Let $0$, $c$ and $1$ be pairwise
distinct elements with $0,c,1\notin X\cup Y$ and
$E=\{\{x_i,y_j\}\mid i\ne j\}$. We define a binary operation $
\odot$ on the set $Z=X\cup Y\cup \{0,c,1\}$ by
$$z\odot w =\left\{\begin{array}{ll} z&\text{ if }w=1,\\
w&\text{ if }z=1,\\
c&\text{ if }\{z,w\}\in E,\\
0&\text{ otherwise.}\end{array}\right.$$ One can easily verify
that $ \mathbf{M}(n)=(Z,\odot ,1)$ is a monoid. Clearly, $X\cup Y$
is a minimal set of generators for $\mathbf{M}(n)$. We prove the following bound.

\paragraph{Proposition 3.7.} For every $n>1$, if
$\phi:\binom{[t]}2\longrightarrow\mathfrak{P}(X\cup Y)$ is a
mapping such that $\End(G(\mathbf{M}(n),\phi))$ is isomorphic to
$\mathbf{M}(n)$, then $\binom t2\geq n$ and
$|V(G(\mathbf{M}(n),\phi))|\geq(2n+3)\sqrt{n}=\Omega(m^{\frac
32})$.

\paragraph{Proof:}Let $\phi:\binom{[t]}2\longrightarrow \mathfrak{P}(X\cup Y)$
with $\phi(j,k)=B_{jk}$ for all $(j,k)\in\binom{[t]}2$. Let us denote
$\mathbf{M}=\mathbf{M}(n)$. The
statement easily follows from the following fact.

\paragraph{Fact.} If $\End(G(\mathbf{M},\phi))\cong\mathbf{M}$, then for all
$i\in[1,n]$ there exist $(j,k),(j',k')\in\binom{[t]}2$ such that
$B_{jk}\cap X=\{x_i\}$ and $B_{j'k'}\cap Y=\{y_i\}$.

\vspace{.1in}

Indeed, if $\End(G(\mathbf{M},\phi))\cong\mathbf{M}$, then for
every $i\in [1,n]$ there exists $(j,k)\in \binom{[t]}2$ with
$B_{jk}\cap X=\{x_i\}$. Consequently, $|\binom{[t]}2|\geq n$ and
hence, the underlying set of $G(\mathbf{M},\phi))$ has cardinality
at least $(2n+3)\sqrt{2n}=\Omega(m^{\frac 32})$. $\Box$


\paragraph{Proof of Fact:} We argue by contraposition, that is, suppose there
exists $i\in[1,n]$ with $\{x_i\}\neq B_{jk}\cap X$ for all
$(j,k)\in {[t]\choose 2}$. If $\{y_i\}\ne B_{j'k'}\cap Y$ for all
$(j',k')\in\binom{[t]}2$ then the proof is analogous.

By Claim 3.54, every left translation of $\mathbf{M}$ is a
determining mapping of $G(\mathbf{M},\phi)$, i.e.
$\mathbf{M}^L\subseteq\mathcal{D}$. Since, by Lemma 3.2,
$\mathbf{M}^L\cong\mathbf{M}$ it suffices to show that there
exists a determining mapping $g\in\mathcal{D}$ which is not a left
translation of $\mathbf{M}$. Consider a mapping $g:Z\rightarrow Z$
such that
$$g(z)=\left\{\begin{array}{ll} y_i&\text{ if }z=1,\\
c&\text{ if }z\in X,\\
0&\text{ if }z\in Y\cup \{0,c\}.\end{array}\right.$$ Observe that
$g$ is not a left translation of $\mathbf{M}$. Indeed, from
$g(1)=y_i$ it follows that if $g$ is a left translation then it is
a left translation by $y_i$. But $g(x_i)=c\ne 0=y_i\odot x_i$ and
hence $g$ is not a left translation by $y_i$.

We show that $g$ is a determining mapping using Lemma 3.53. Fix
$z\in Z,~(j,k)\in {[t]\choose 2}$ and $a\in\phi (j,k)$. First
assume $ z\ne 1$. Then $za\in \{c,0\}$ and hence $g(za)=0$. Since
$g(z)\in \{c,0\}$ and $ a\neq 1$ we conclude that $g(z)a=0$ and
the condition from Lemma 3.53 is fulfilled with $b=a$. Secondly,
assume that $z=1$. If $a\in Y$ then $g(z)a=0$ and $g(za)=g(a)=0$
and again it suffices to set $b=a$. If $a\in X$ then
$g(za)=g(a)=c$. From $\{x_i\}\ne B_{jk}\cap X$ it follows that
there exists $a'\in B_{jk}\cap X$ with $a'\ne x_i$. Then
$g(z)a'=y_ia'=c$ and the condition of Lemma 3.53 is fulfilled.
Thus, $g$ is a determining mapping and $\End(G(\mathbf{M},\phi))$
is not isomorphic to $\mathbf{M}$. $\Box$
