\mychapter{Introduction}
\setcounter{page}{1}


This work is concerned with properties of finite graphs. We shall assume the reader is familiar
with the basic definitions and concepts of Graph Theory [W]. The following will be of central importance.

\paragraph{Definition.}An \emph{endomorphism} of a (finite) graph $G$ is a function
$f:V(G)\rightarrow V(G)$ where $f(x)f(y)\in E(G)$ whenever $xy\in E(G)$.
\vspace{.1 in}

We recall some algebraic concepts: given a nonempty set $S$ and an associative binary operation
$\cdot$ on $S$, $\mathbf{S}=(S,\cdot )$ is a
\emph{semigroup}. If there exists an element $e\in S$ such that
$xe=ex=x$ for all $x\in S$ then we say that $e$ is the
\emph{unity} of $\mathbf{S}$ and $\mathbf{S}$ is a \emph{monoid}.
We recall that a \emph{transformation} \emph{monoid} on a set $X$
is a set of mappings $f:X\longrightarrow X$ closed under
composition and containing the identity mapping. For a monoid we
shall write $\mathbf{M}=(X,\cdot ,e)$ where $e$ is the unity of
$\mathbf{M}$. If $\mathbf{S}=(S,\cdot )$ is a semigroup then
$\mathbf{S}^1=(S\cup \{1\},\cdot ,1)$ is a monoid where $1$ is a
new element (i.e. $1\notin S$) and the operation $\cdot$ is
extended to $S\cup \{1\}$ such that $1\cdot 1=1$ and $x1=1x=x$ for
all $x\in S$. The set of all endomorphisms of any graph $G$, along
with the identity endomorphism, form a monoid under composition
(the so called \emph{endomorphism} \emph{monoid} of $G$).

In [F1] and [F2] Frucht proved that every finite group is
isomorphic to the automorphism group of some finite graph. The analogous result for monoids
was given by Hedrl\'\i n and Pultr [HP1,HP2] (or [PT]) who
proved that for any monoid $\mathbf{M}$ there exists a graph $G$
such that $\End(G)$ is isomorphic to $\mathbf{M}$ and if
$\mathbf{M}$ is finite then we can assume that $G$ is finite as
well. This result inspired many analogous theorems for restricted
classes of graphs. For a good survey see the monograph by Pultr
and Trnkov\'a [PT].

\vspace{.1 in}

Our main goal is to give bounds on the minimum number of edges and
vertices required to realize a given monoid as the endomorphism
monoid of a graph. For a monoid $\mathbf{M}$ let $\nu(\mathbf{M})$
denote the least number $n$ such that there exists a graph $G$ of
order $n$ with $\End (G)\cong\mathbf{M}$. Analogously, for
$\alpha\in (0,1]$ we define $\nu(\mathbf{M},\alpha)$ with the
added restriction that $G$ has at most $n^{1+\alpha}$ edges.
Observe that $\nu (\mathbf{M})=\nu (\mathbf{M},1)$. Likewise, let
$\varepsilon (\mathbf{M})$ denote the least number $s$ such that
there exists a graph $G$ with $s$ edges and $\End
(G)\cong\mathbf{M}$. For a class of monoids $\mathcal{M}$ we set
\begin{align*}
\nu_{\mathcal{M}}(m)&=\max_{|X|=m}\{\nu (\mathbf{M})\mid
\mathbf{M}=(X,\cdot
,1)\in\mathcal{M}\},\\
\nu_{\mathcal{M}}(m,\alpha)&=\max_{|X|=m}\{\nu
(\mathbf{M},\alpha)\mid\mathbf{M}=(X,\cdot
,1)\in\mathcal{M}\},\\
\varepsilon_{\mathcal{M}}(m)&=\max_{|X|=m}\{\varepsilon
(\mathbf{M})\mid\mathbf{M}=(X,\cdot
,1)\in\mathcal{M}\}.\end{align*} If $\mathcal{M}$ is the class of
all monoids then we shall omit the index $\mathcal{M}$.

From a result of Hedrl\'\i n and Pultr [HP3], it follows that $\nu
(m)\leq m$ for any infinite cardinal $m$ and by a counting
argument we immediately obtain that, under GCH, $\nu (m)=m$ for
any infinite cardinal $m$. It is an open question whether there is
a model of set theory in which $\nu (m)<m$ for some infinite
cardinal $m$.

In what follows we will restrict ourselves to the finite case. From
results of Hedrl\'\i n and Pultr [HP1] it follows that $\nu
(m)\leq cm^2$ for some $c>0$. On the other hand, Babai [B1] showed
that for any finite group $\mathbf{H}$ distinct from the cyclic
groups of order $4$, $5$ and $6$, there exists a finite graph $G$
such that the group of all automorphisms of $G$ is isomorphic to
$\mathbf{H}$ and $|V(G)|=2|\mathbf{H}|+1$. This motivated the
question, posed by Babai and Ne\v set\v ril, of whether there
exists a constant $c$ such that $\nu (m)\leq cm$. This was
answered in the negative in [KR1] by showing that $\nu (m)\geq
(\sqrt{2}+o(1))(m\sqrt{\log m})$. In fact, one can show an
analogous result for a subclass of monoids. A monoid
$\mathbf{M}=(X,\cdot ,e)$ is called \emph{three}-\emph{nilpotent}
if $\mathbf{M}$ has a zero $0$ and $abc=0$ for all $a,b,c\in
X\setminus \{e\}$. Let $\mathcal{CN}$ denote the class of all
finite, commutative three-nilpotent monoids. We show that
$\nu_{\mathcal{C}\mathcal{N}}(m)\geq(1+o(1))m\sqrt{\log m}$.

An upper bound on $\nu$ was obtained by Babai [B2] and,
independently, by Koubek and R\"{o}dl in [KR1], where $\nu (m)\leq
(\sqrt{2}+o(1))m^{\frac{3}{2}}$ was attained (the Babai bound is of the same order).
In [KR1] it was also proved that $\nu_{\mathcal{N}}(m)\leq O(m\log m)$ where
$\mathcal{N}$ denotes the class of all finite three-nilpotent
monoids. Our aim is to give some related results.

\vspace{.1 in}

In Chapter 2 we give a lower bound on $\varepsilon (m)$, as well
as some other related lower bounds which follow from basic
counting arguments. Specifically, we show that:

\paragraph{Theorem 1.}For all $m,~\frac{m^2}{2}(1+o(1))\leq\varepsilon (m)\leq(1+o(1))m^2$.
\vspace{.1 in}


\paragraph{Theorem 2.}For all $m,~(1+o(1))\left(\frac{1+\alpha}{2}\right)^{\frac{1}{1+\alpha}}
m^{\frac{2}{1+\alpha}}\leq \nu(m,\alpha)\leq
(1+o(1))m^{\frac{2}{1+\alpha}}$\\ where the lower bound holds for
$\alpha\in (0,1]$ and the upper bound holds for $\alpha\in
(0,\frac{1}{3})$.

\vspace{.1 in}
Note that while the upper and lower bounds on $\nu(m)$ are still far apart, the bounds
on $\varepsilon (m)$ and $\nu(m,\alpha)$ are only separated by a
constant.

In Chapter 3 we introduce some \textit{ad hoc} tools and give an explicit
construction for a graph on $n\leq O(m^{\frac{3}{2}})$ vertices
with prescribed endomorphism monoid. The upper bounds in Theorems
1--6 are all a consequence of said construction. We also give an
example of a monoid which shows that the upper bound of $O(m^{\frac{3}{2}})$ cannot
be improved using  our construction.

We were unable to improve the general
upper bound on $\nu(m)$. However, it is known that for 3-nilpotent monoids, which almost all monoids are
(see [KR2]), the upper bound can be significantly improved (see
[KR1]). This led us to consider other special classes. This discussion begins in Chapter 4 where classes of monoids
based on groups are considered. Let $\mathcal{G}$ denote the class of all finite
groups. We prove that

\paragraph{Theorem 3.}$\nu_{\mathcal{G}}(m)\leq (2+o(1))m\sqrt
{\log\log m}$. \vspace{.1 in}

We observe that such graphs, with endomorphism monoid isomorphic to a group, are cores. A comparison of this result with Babai's result [B1] for
automorphism groups leads to the following open problem.

\paragraph{Problem:}Is there a constant $c$ such that
$\nu_{\mathcal{G}}(m)\leq cm$? \vspace{.1 in}

We investigated two generalizations of groups. Given nonempty sets $B$ and $C$
and a group $\mathbf{H}$ let $S=(B\times H\times C,\cdot)$ and define a binary operation $\cdot$
on $S$ by $(b,h,c)\cdot (b',h',c')=(b,hh',c')$. Then $\mathbf{S}=(S,\cdot)$ is a monoid known, unfortunately, as a
\emph{rectangular} \emph{group} (see monographs of semigroups [CP]
and [H]).Let $\mathcal{R} \mathcal{G}$ be the class of all monoids
$\mathbf{M}=\mathbf{S}^1$ where $\mathbf{S}$ is a finite
rectangular group. Then:

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

The second generalization of groups are $k$-right cancellative
monoids. For a natural number $k\geq 1$ we say that a monoid
$\mathbf{M}=(X,\cdot ,e )$ is $k$-\emph{right} \emph{cancellative}
if $|\{y\in X\mid xy=x'\}|\leq k$ for all $x,x'\in X$ and
\emph{weakly} $k$-\emph{right} \emph{cancellative} if for some
generating set $A$, $|\{a\in A\mid xa=x'\}|\leq k$ for all
$x,x'\in X$. Clearly, every $k$-\emph{right} \emph{cancellative}
monoid is \emph{weakly} $k$-\emph{right} \emph{cancellative}.
Also, it is well-known that $H$ is a group if and only if it is
$1$-cancellative. Let $\mathcal{C}_k$ be the class of all finite,
weakly $k$-right cancellative monoids. It follows from a simple
probabilistic argument that:

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

\vspace{.1 in}

Note that this result is weaker for finite groups than Theorem~3. In
the last section of Chapter 4 we investigate the class
$\mathcal{C}\mathcal{S}$ of all monoids $\mathbf{M}=\mathbf{S}^1$
where $\mathbf{S}$ is a finite, completely simple semigroup (the
precise definition is given in the relevant section). Completely
simple semigroups -- see [CP], the third chapter, or [H] -- are
the basic building blocks used in a structural description of
semigroups. We prove:

\paragraph{Theorem 6.}For all $m,~\nu_{\mathcal{C}\mathcal{S}}(m)\leq (2+o(1))m^{\frac
{7}{6}}$.

\vspace{.1 in}


In Chapter 5 we will generalize the $\mathcal{P}$-graph construction (to be defined) from Chapter 3 in order to
derive bounds for new monoid classes. Among these are the so called ``strong semilattices
of $C$-semigroups" where $C$ is one of the following: groups,
abelian groups, rectangular groups or completely simple
semigroups. Our general approach will be as follows. Suppose $\{M^{(i)}\mid i\in
I\}$ is a collection of monoids with $\nu(M^{(i)})$ ``small" for
all $i\in I$ and $M$ is a subdirect product of the $M^{(i)}$. Then
we can extend the $\mathcal{P}$-graph construction to
products and derive a bound on $\nu(M)$ in terms of the
$\nu(M^{(i)})$ which substantially improves the bound we would
have gotten from applying our earlier construction directly to
$M$. We will apply these tools to three particular
classes; finite abelian groups denoted $\mathcal{A}$, finite
normal band monoids denoted $\mathcal{NB}$, and finite semilattice
monoids denoted $\mathcal{L}$. Formal definitions for each class
will be given in Chapter 5. For now we point out that finite
abelian groups and semilattices are subdirect products of cyclic
groups and two-element semilattices, respectively. Normal bands,
like semilatices, are also subdirect products with factors from a
finite collection to be described later.

\paragraph{Theorem 7.} Let
$\mathcal{M}$ be any of the classes
$\mathcal{L},~\mathcal{A},~\mathcal{NB}$. Then
$$\nu_{\mathcal{M}}(n)=O(n).$$


\noindent In Chapter 5 we will determine more precise constants for each
class.

The result for abelian groups modifies the result
$$\nu_{\mathcal{G}}(n)\leq (2+o(1))n\sqrt {\log\log n}$$ of Theorem 3
for the class $\mathcal{G}$ of finite groups.  Note, also, that
our result for abelian groups is distinct from the Babai result
[B1] mentioned above as we require that our graph have no
proper endomorphisms.


The last chapter is devoted to classes of monoids built out of semigroups and semilattices.
This construction was intensely
studied in the monograph by Petrich [P]. We will show that the resulting object, the so called
strong semilattice of semigroups, can be handled by
our construction.

For a collection $\mathcal{C}$ of semigroups we shall write
$\mathfrak{S}(\mathcal{C})$ for the class of monoids which are
either strong semilattices of $\mathcal{C}$-semigroups or are
strong semilattices of $\mathcal{C}$-semigroups with added new
identity. We will consider several cases for $\mathcal{C}$: groups
$\mathcal{G}$, abelian groups $\mathcal{A}$, rectangular groups
$\mathcal{RG}$ and, completely simple semigroups $\mathcal{CS}$.
We shall define these classes precisely in Chapter 5.


In the last chapter we will prove:

\paragraph{Theorem 8.} The following bounds hold for strong
semilattices of $\mathcal{C}$-semi\-groups
\begin{eqnarray*}\nu_{\mathfrak{S}(\mathcal{A})}(n)\leq 21n,&\qquad&\nu_{\mathfrak{S}(\mathcal{G}
)}(n)\leq(2+o(1))n\sqrt {\log\log n},\\
\nu_{\mathfrak{S}(\mathcal{RG})}(n)\leq(2+o(1))n\sqrt {\log
n},&\qquad& \nu_{\mathfrak{S}(\mathcal{CS})}(n)=(2+o(1))n^{\frac
76}.\end{eqnarray*}


We conclude our introduction with Figure 1.1, a diagram for the
classes of semigroups considered here ordered by
inclusion.



\begin{figure}
 \centering
 \epsfxsize=4in
 \epsfysize=6in
  \epsfbox{the-3.4}
 \caption{Poset of semigroup classes}
\end{figure} 