\mychapter{Lower Bounds}

We begin by proving the lower bounds from Theorems 1 and 2.

\paragraph{Theorem 1 -- Lower Bound.}For all $m,~\varepsilon (m)\geq \frac{m^2}{2}(1+o(1))$.
\paragraph{Proof:}
We begin by observing that a graph with $m$ endomorphisms has at most $t$ isolated vertices
whenever $t^t>m$ (which implies $t=(1+o(1))\frac{\log m}{\log\log m})$.Let $G$ be a graph with $\End (G)\cong\mathbf{M}=(X,\cdot,e)$
where $|X|=m$ and $|E(G)|=q$. By our observation $|V(G)|<2q+t$. We will use this to bound $q$ from below.

The number of (labeled) graphs with at most $q$
edges and at most $2q+t$ vertices is
\begin{align*}\sum_{j=0}^{2q+t}\sum_{i=0}^{q}{{j\choose 2}\choose
i} &< (2q+t)q{{2q+t\choose 2}\choose q}\\ &<(2q+t)q\left[\frac{(2q+t)^2e}{2q}\right]^q~~~~~~~~~~~(\ast)
\end{align*}

As any $m$-element monoid can be represented by a graph counted in $(\ast)$ this quantity must exceed $m^{m^2(1+o(1))}$, the
number of monoids on $m$ elements [KRS] (see also [KR2]). Taking logarithms we get,

$$\log [(2q+t)q]+q\log\left[\frac{(2q+t)^2e}{2q}\right]>m^2\log m(1+o(1))~~~~~~~~~~~(\ast\ast)$$

substituting $q=\frac{m^2}{2}(1+o(1))$ and $t=(1+o(1))\frac{\log m}{\log\log m}$ the left-hand side of  $(\ast\ast)$
becomes


$$\log{\frac{m^2}{4}}+\frac{m^2}{2}\log (m^2)(1+o(1))=m^2\log m(1+o(1))$$
as required. Thus, $\epsilon(m)$ which is at least the minimum
$q$ satisfying the above inequality, is greater than $\frac{m^2}{2}(1+o(1))$. $\Box$

\vspace{.1 in}


\paragraph{Theorem 2 -- Lower Bound.}For all $m$ and $\alpha\in (0,1],~\nu(m,\alpha)\geq
(1+o(1))\left(\frac{1+\alpha}{2}\right)^{\frac{1}{1+\alpha}}
m^{\frac{2}{1+\alpha}}$.

\paragraph{Proof:} The lower bound follows
from a counting argument analogous to the one used in proving
Theorem 1. Let $n=\nu(M,\alpha)$. The number of sufficiently sparse graphs on at most $n$ vertices
is given by
$$\sum_{j=0}^{n}\sum_{i=0}^{j^{1+\alpha}}{{j\choose 2}\choose
i}\leq n^{2+\alpha}\left(\frac{n^2}{2n^{1+\alpha}}e\right)^{n^{1+\alpha}}$$
which, for sufficiently large $n$, is less than  $n^{n^{1+\alpha}}$.
By assumption every monoid of size at most $m$ is represented by
one of the $n^{n^{1+\alpha}}$ graphs and so
$$n^{n^{1+\alpha}}\geq m^{m^2(1+o(1))}$$ which is equivalent to
$$n(\log n)^{\frac {1}{1+\alpha}}\geq (\log m)^{\frac {1}{1+\alpha}}
m^{\frac {2}{1+\alpha}}(1+o(1)).~~~~(\ast)$$ For each $m$,
the minimum real number $n_0=n_0(m)$ for which $(\ast)$ holds
satisfies $$\frac{\log m}{\log n_0}=\frac {1+\alpha}{2}(1+o(1)).$$
Combining this equality with $(\ast)$ yields that for each $m$
$$n\geq n_0(m)=(1+o(1))m^{\frac 2{1+\alpha}}\left(\frac{\log m}{\log n_0}\right)^{\frac 1{1+\alpha}}=(1+o(1))\left(\frac{1+\alpha}{2}\right)^{\frac{1}{1+\alpha}}
m^{\frac{2}{1+\alpha}}.~ \Box$$
\vspace {.1 in}


\paragraph{Remark:}The only other result in this work regarding edges is Proposition 3.6.
There we improved the constant term from 15 to 7 in the following result of Hedrl\'\i n and Pultr.
For any monoid $\mathbf{M}=(X,\cdot,1)$ there exists a graph $G$ with at
most $(15+o(1))m$ edges such that $\End(G)\cong \mathbf{M}$. It may be of interest to find
the smallest constant with this property.

\vspace{.1 in}

Finally, we modify the lower bound on $\nu_{\mathcal{N}}(m)$ from
[KR1] for commutative monoids. We recall that a monoid
$\mathbf{M}=(X,\cdot,1)$ is commutative $3$-nilpotent if
$\mathbf{M}$ has a zero $0$ and $abc=0$ for all triples
$\{a,b,c\}$ where $a,b,c\in X\setminus\{1\}$ and $ab=ba$ for all
$a,b\in X$. Let $\mathcal{C}\mathcal{N}$ be the class of all
finite, commutative $3$-nilpotent monoids. Then:

\paragraph{Theorem 2.1.}For all $m,~\nu_{\mathcal{C}\mathcal{N}}(m)\geq(1+o(1))m\sqrt{\log m}.$

\paragraph{Proof:}The proof is a simple modification of the proof in [KR1]
where a similar argument was used to bound the number of all (not
necessarily commutative) semigroups. Let $X$ be an $m$-element set
and $e\in X$. Let $X\setminus\{e\}=A\cup B$ be a partition. Select
an element $0\in B$ and a mapping $g:A\times A\longrightarrow B$ such that $g(x,y)=g(y,x)$ for all $x,y\in A$.
We define a binary operation by
\begin{displaymath}x\cdot y=\left\{\begin{array}{ll}x & \text{if}~y=e,\\
y & \text{if}~x=e,\\0 & \text{if}~x\in B\text{\ or}~y\in
B,\\g({x,y}) & \text{if}~x,y\in
A.\end{array}\right.\end{displaymath}

A routine verification
yields that $(X,\cdot,e)$ is a $3$-nilpotent commutative monoid
and for distinct mappings $g_1$ and $g_2$ we obtain distinct
monoids. For a fixed $A$ with $|A|=t$ there exist $(m-t-1)^{\binom
t2+t}$ symmetric mappings and hence we have at least
$$\frac 1{m!}m\binom {m-1}t(m-t-1)^{\binom t2+t}>\frac 1{m!}(m-t-1)^{\frac 12t^2}$$
non-isomorphic monoids of this type.

Setting $t=m-\frac m{\log m}$ then yields at least
$$\frac 1{m!}(\frac m{\log m}-1)^{\frac 12(m-\frac m{\log m})^2}=2^{(\frac 12+o(1))m^2\log m}$$
non-isomorphic monoids. As in Theorems 1 and 2 we compare this
quantity with the number of all graphs on an $n$-element set,
obtaining
$$2^{n\choose 2}\geq 2^{\frac{m^2}{2}\log m(1+o(1))}$$ which yields
$$\nu_{\mathcal{CN}}(m)=n\geq(1+o(1))m\sqrt{\log m}.~ \Box$$

\vspace {.1 in}

The remainder of this work is concerned with upper bounds on $\nu
(m)$. In what follows we describe a construction for a graph
$G=G(\textbf{M})$ on less than $O(m^\frac{3}{2})$ vertices with a
prescribed endomorphism monoid $\textbf{M}$ and at most $m^2$
edges.



