\section{Introduction}



For studying finite structures  it is helpful to generate small examples by computer programs.
By investigating these sample objects we can formulate new hypotheses and falsify conjectures by counterexamples.
At a given time, the available computing power and the state of the art algorithms define a limit on the size of the examples we can investigate.
This limit we call the \emph{computational horizon}, similar to the cosmological horizon determined by the size of our observable physical universe.
 The underlying assumption in both fields is that we can see enough within our limits to enable us to go beyond by theoretical reasoning, i.e.~to have enough observational data to construct valid theories. Here we aim to extend the database of small degree diagram semigroups. 


\section{Diagram Semigroups}

Diagram representations of finite semigroups are described by fundamental mathematical objects such as relations and functions, and so they often arise naturally in mathematical theories.
The original interest came from algebras with a basis whose elements can be multiplied diagrammatically (e.g.~\cite{Brauer1937,Jones1994,Martin1994}).

In what follows, we define diagram semigroups in a logical order (as opposed to a historical order) starting with the most general diagram type and define each type by a set of constraints.
The conceptual origin of diagram semigroups is the notion of binary relation on a set $A$.
Such a relation, a subset of $A\times A$, can be represented as a graph by a set of directed edges between the elements of $A$ as vertices.
In order to make the graph of a binary relation into a diagram that can be combined with other diagrams we partition $A$ into two parts.
The \emph{domain} $\Dom(A)$ and \emph{codomain} $\Codom(A)$ are the ``interfaces'' for combining diagrams.
In general we can talk about $(n,m)$ diagrams, where $n$ is the size of the domain and $m$ is the size of the codomain and $|A|=n+m$. 
Here, we restrict our attention to $(n,n)$ diagrams, so we partition $A$ into to equal sized parts. 


\subsection{Partitioned Binary Relations}

Partitioned binary relations are the most general type of diagrams we consider, although historically it was the last to be defined. For the formal definitions and its categorical context see \cite{PartBinRel2013}.

For a finite set $X$ a \emph{diagram} is a subset of $(X\cup X')\times (X\cup X')$ where $|X|=|X'|=n$, the \emph{degree} of the diagram, and $X\cap X'=\varnothing$. 
Pictorially, we draw the points from $X$ on an upper row with those from $X'$ below, and we draw a directed edge $a\to b$ for each pair $(a,b)$ from the diagram.  For example, with $X=\{1,2,3,4,5\}$, the diagram
$\big\{
(2,1),
(2,3'),
(5,4'),
(5,5'),
(1',1),
(2',2'),
(2',3),
(3',4'),
(4',3'),
(5',5)
\big\}$
is pictured as the top diagram of Figure \ref{fig:diagram_semigroup_types}.

The product $\alpha\beta$ of two diagrams $\alpha$ and $\beta$ (on the same set $X$) is calculated as follows.  We first modify $\alpha$ and $\beta$ by changing every lower vertex $x'$ of $\alpha$ and every upper vertex $x$ of $\beta$ to $x''$.  We then stack these modified diagrams together with $\alpha$ above $\beta$ so that the vertices $x''$ are identified in the middle row (there may now be parallel edges in this stacked graph).  Finally, for each $a,b\in X\cup X'$ we include the edge $a\to b$ in $\alpha\beta$ if and only if there is a path from $a$ to $b$ in the stacked graph (as defined above) for which the edges used in the path alternate between the edges of $\alpha$ and the edges of $\beta$.  An example is given in Figure \ref{fig:PartBinRelMult} (where, for convenience, the edges of $\beta$ are white so that the kinds of paths referred to above are alternating in colour).  This operation is associative, so the set of all diagrams on the set $X$ forms a semigroup.  When $X=\{1,2,\ldots,n\}$, we denote this semigroup by $\Partition\BinRel_n$.  The identity element of $\Partition\BinRel_n$ is the diagram containing the edges $x\to x'$ and $x'\to x$ for each $x$ (see Figure \ref{fig:idpartbinrel}).

\begin{figure}[h]
\begin{center}
\input{tikz/PartBinRelMult.tikz}
\end{center}
\caption{Combining partitioned binary relations $\alpha$ and $\beta$. The arrows of the product are induced by paths of the stacked diagram with the property that the consecutive arrows have alternating colors.}
\label{fig:PartBinRelMult}
\end{figure}

\begin{figure}
\begin{center}
\input{tikz/IdentityPartBinRel.tikz}
\end{center}
\caption{The identity partitioned binary relation.}
\label{fig:idpartbinrel}
\end{figure}

Subsemigroups of $\mathcal P\text{B}_n$ are the \emph{diagram semigroups} of degree $n$.
Imposing different sets of constraints on the diagrams gives rise to different kinds of diagram semigroups (example diagrams are shown in Figure~\ref{fig:diagram_semigroup_types}). There are two main ways to specialize the diagrams. We can restrict the arrows to go only one way from top to bottom, domain to codomain, yielding binary relations and then different functions, the classical transformation semigroups \cite{ClassicalTransSemigroups2009}. We can also consider partitioned binary relations that are equivalence relations, yielding the partition monoid and its submonoids.

\begin{figure}[h]
\begin{center}
\input{tikz/ExamplePartBinRel.tikz}
\vskip6pt
\input{tikz/ExampleBinRel.tikz}
\input{tikz/ExamplePartition.tikz}
\vskip6pt
\input{tikz/ExamplePartial.tikz}
\input{tikz/ExampleDualInvMon.tikz}
\vskip6pt
\input{tikz/ExamplePartialPerm.tikz}
\input{tikz/ExampleBrauer.tikz}
\vskip6pt 
\input{tikz/ExampleTrans.tikz}
\input{tikz/ExampleTL.tikz}
\vskip6pt
\input{tikz/ExamplePerm.tikz}
\input{tikz/ExampleIdentity.tikz}
\end{center}
\caption{Typical elements of different types of diagram semigroups. Undirected edges represent a pair of opposite direction arrows.}
\label{fig:diagram_semigroup_types}
\end{figure}


\subsection{Binary Relations}

Prohibiting edges within the upper and lower sets and restricting to top-down edges yields $\text{B}_n$, the monoid of binary relations of an $n$-element set \cite{plemmons1970}. 

It is tempting to think that degree $n$ partitioned binary relations can be represented by binary relations of degree $2n$. This is true on the level of elements, but not on the semigroup level, since multiplication is different.
\subsection{Partial and Total Transformations}

Further constraints give us partial transformations (for each $x$, there is at most one edge $x\to y'$); transformations (for each $x$, there is exactly one edge $x\to y'$); partial permutations (injective partial transformations); and permutations (injective transformations).  The sets of all such elements are, respectively: the partial transformation semigroup $\text{P}\FullTrans_n$, the (full) transformation semigroup $\mathcal T_n$; the symmetric inverse semigroup $\mathcal I_n$; and the symmetric group $\mathcal S_n$.

\subsection{Symmetric Group and Symmetric Inverse Monoid}

Degree $n$ permutations form the symmetric group $\mathcal S_n$, a central and thoroughly studied algebraic structure (e.g.~\cite{CameronPermGroups99, DixonMortimerPermGroups96}).
Partial permutations form the \emph{symmetric inverse monoid} \cite{lawson1998inverse}.

\subsection{Partitions}

If the underlying relation is an equivalence relation then we have the \emph{partition monoid} $\mathcal P_n$ \cite{PartitionAlgebras2005}, also known as the \emph{bipartition monoid}.
When drawing its diagrams we can omit loop edges due to reflexivity, and a pair of directed edges can be replaced by an undirected one due to the relation being symmetric.
We also use the transitivity of the equivalence relation and draw fewer edges.

\subsection{Dual Symmetric Inverse Monoid} 

The equivalence relation of a partition diagram $\alpha$ defines quotient sets of $\Dom(\alpha)$ and $\Codom(\alpha)$, sets of \emph{blocks}.
If the diagram induces a bijection between the upper and the lower set of blocks, then the diagram is a \emph{block bijection}. The monoid consisting of these block bijections is called the dual symmetric inverse monoid, since it is the categorical dual of the symmetric inverse monoid \cite{DualSymmetricInverse1998}.


\subsection{Brauer Diagrams}

Restricting to partitions of size 2 only, we get the Brauer monoid $\mathfrak B_n$.

\subsection{Temperley-Lieb Diagrams}

Restricting to planar diagrams from $\mathfrak B_n$ we get the Temperley-Lieb monoid $TL_n$.


\subsection{The big picture}

Transformations and partial permutations and the dual symmetric inverse monoid ${\mathcal I}^*_n$ also embed into $\mathcal P_n$, but $P\mathcal T_n$ does not (its elements can be realized with diagrams of $\mathcal P_n$, but the multiplication is different).
Relationships between the diagram monoids are shown by the Hasse diagram in Figure~\ref{fig:names}, with edges denoting restrictions of rules of definition and consequently embeddings.

Some  results about diagram representations of semigroups are known.
For instance, it is trivial that the semigroup of \emph{partial transformations} $\text{P}\FullTrans_n$ embeds into the semigroup of transformations $\mathcal T_{n+1}$, so we can avoid partial maps by adding one more point.
Less trivially, it has recently been shown that in the weaker sense of generating the corresponding pseudovarieties, the Brauer monoid $\mathfrak B_n$ can represent all monoids, while the Temperley-Lieb monoid $\text{TL}_n$ can represent all aperiodic semigroups \cite{BrauerTypeMonoids}.


\begin{figure}
\input{tikz/DiagramSemigroupPoset.tikz
\begin{tabular}{cl}
\hline
Symbol & Name and References\\ 
\hline 
$\Partition\BinRel_n$& Partitioned binary relations \cite{PartBinRel2013}\\
\rowcolor[gray]{0.925} 
$\text{B}_n$& Binary relations \cite{plemmons1970}\\
$\text{P}\FullTrans_n$& Partial transformation semigroup \cite{ClassicalTransSemigroups2009}\\
\rowcolor[gray]{0.925} 
$\mathcal P_n$&(Bi)partition monoid \cite{PartitionAlgebras2005}\\
$\mathfrak B_n$&Brauer monoid\\
\rowcolor[gray]{0.925} 
$\mathcal S_n$&Symmetric group\cite{CameronPermGroups99, DixonMortimerPermGroups96}\\
$\mathcal T_n$&Full transformation semigroup \cite{ClassicalTransSemigroups2009}\\
\rowcolor[gray]{0.925} 
$\mathcal I_n$&Symmetric inverse monoid \cite{lawson1998inverse}\\
${\mathcal I}^*_n$&Dual symmetric inverse monoid \cite{DualSymmetricInverse1998}\\
\rowcolor[gray]{0.925} 
$TL_n$ & Temperley-Lieb, Jones monoid $J_n$\\
\end{tabular}
\caption{Summary table of diagram semigroups: notation, names and references. \todo{refs for all}}
\label{fig:names}
\end{figure}


The size of each kind of monoid grows quickly with the degree for diagram semigroups (Tab.\ \ref{tab:sequences}), so brute-force enumeration of all subsemigroups is only possible for small semigroups.

\begin{table}
\begin{tabular}{clrrrrrr}
\hline
 &Order &$n=1$ & $n=2$ & $n=3$ & $n=4$ & $n=5$ & $n=6$ \\ 
\hline 
$\Partition\BinRel_n$& $2^{(2n)^2}$ & $16$ & 65536 &$2^{36}$ & $2^{64}$ & $2^{100}$& $2^{144}$ \\
\rowcolor[gray]{0.925} 
$\text{B}_n$& $2^{n^2}$ & 2 & 16&512&65536&$2^{25}$& $2^{36}$ \\
$\mathcal P_n$&$B_{2n}=\sum_1^{2n} S(2n, k)$ & 2 & 15&  203& 4140&115975 & 4213597\\
\rowcolor[gray]{0.925} 
$\text{P}\FullTrans_n$& $(n+1)^n$ & 2& 9& 64& 625& 7776&117649\\
${\mathcal I}^*_n$&$\sum_1^n k!\big(S(n, k)\big)^2$& 1& 3& 25& 339& 6721& 179643\\
\rowcolor[gray]{0.925} 
$\mathcal T_n$&$n^n$ & 1&4&27&256&3125& 46656\\
$\mathcal I_n$&$\sum_0^n k!{n\choose k}^2$ &2& 7& 34& 209& 1546& 13327\\
\rowcolor[gray]{0.925} 
$\mathfrak B_n$&$(2n-1)!!$ & 1& 3& 15& 105& 945&10395\\
$\mathcal S_n$&$n!$ & 1& 2& 6& 24& 120& 720\\
\rowcolor[gray]{0.925} 
$TL_n,J_n$ & $C_n=\frac{1}{n+1} {2n \choose n}$ & 1&2&5&14&42& 132\\
\hline
\end{tabular}
\caption{Summary table of diagram semigroups. ($C_n$ is the $n$-th Catalan number, $S(n,k)$ are the Stirling numbers of the second kind, $B_n$ is the $n$-th Bell number)}
\label{tab:sequences}
\end{table}



\section{Semigroup Enumeration}
The enumeration of semigroups by computers started very early in computing history, and continuing efforts were focused on constructing abstract semigroups by finding all associative multiplication tables up to isomorphism and anti-isomorphism  of the given size \cite{For55, tamura1, tamura2, Ple67,KRS76,JW77,SZT94,monoidenum2009,ord10semigroups}.
The generated data sets are conveniently available  in the \textsc{Gap}~\cite{GAP4} package called \textsc{SmallSemi}~\cite{smallsemi}.

As a next step, following the success story of computational group theory, where permutation group representations have efficient algorithms, basic algorithms for calculating with finite transformation semigroups were developed.  These cover, for instance, multiplying transformations, enumerating elements, deciding membership, and calculating the divisibility relations and the principal ideals, the so called $\mathcal D$-class structure~\cite{Linton1998aa}.
Currently \textsc{Gap}~\cite{GAP4} and its \textsc{Semigroups}~package \cite{Semigroups} have the implementations of these algorithms.

In algebraic automata theory, finite automata are represented as transformation semigroups. 
Interest in studying finite computations led to the enumeration of transformation semigroups up to degree 4 by enumerating all subsemigroups of $\mathcal T_4$.
This was achieved by dividing up the semigroup along its ideal structure, allowing parallel processing \cite{SubSemi2014}.
An \emph{ideal} is a subsemigroup $I\leq S$ such that $SI\subseteq I$ and $IS\subseteq I$.
By using Rees-quotients~\cite{clifford_preston,Howie95}, we can collapse an ideal to a zero element, substantially reducing the search space by separating it into two parts, the ideal $I$ and the quotient semigroup $S/I$.
This algorithm is implemented in the \textsc{SubSemi}~package \cite{subsemi}. 

The strategy of taking the all enveloping full structure and enumerating its substructures can be used for all kinds of diagram representations.
Moreover, recently the fundamental semigroup algorithms have been generalized to partial permutation semigroups, partition monoids, matrix semigroups, and subsemigroups of finite regular Rees matrix and
$0$-matrix semigroups~\cite{Semigroups,citrus}. These two facts made the computational enumeration of finite diagram semigroups possible.   

The simplest way of compressing enumeration data is to consider only conjugacy class representatives. Two diagrams are conjugate if they differ only by a reordering of their points. We denote the set of conjugacy class representatives of the semigroup $S$ by $\mathbf{Sub}_G(S)$, where $G$ is the permutation group of all permutations of the underlying points that preserves the semigroup $S$. 

\section{Visualising the Database}
\begin{table}
\begin{tabular}{rrrrrrr}
\hline
& $n=1$ & $n=2$ & $n=3$ & $n=4$ & $n=5$ & $n=6$\\
\hline
$\Partition\BinRel_n$ & 1262 & & & & & \\
\rowcolor[gray]{0.925}
$\text{B}_n$ & 4 & 385 &  &  & & \\
$\mathcal P_n$ & 4 & 272 &  &  & & \\
\rowcolor[gray]{0.925} 
$\text{P}\FullTrans_n$ & 4 & 50 & 94232 & & & \\
$\mathcal I_n$ & 4 & 23 & 2963 & & & \\
\rowcolor[gray]{0.925} 
${\mathcal I}^*_n$ & 2 & 6 & 795 & & & \\
$\mathcal T_n$ & 2 & 8 & 283 &132069776 & & \\
\rowcolor[gray]{0.925} 
$\mathfrak B_n$ & 2 & 6 & 42 & 10411 & & \\
$\text{TL}_n$ & 2 &4 &12 &232& 12592 & 324835618\\ 
\rowcolor[gray]{0.925}
$\mathcal S_n$ & 1 &2 &4 &11& 19 & 56\\ 
\end{tabular}
\caption{Summary table of the numbers of distinct (up conjugacy) semigroups of given diagram type and degree.}
\label{tab:limits}
\end{table}

The first thing we would like to know about a type of combinatorial structure is to know how many there are.
The known values for the numbers of diagram semigroups of degree $n$  are summarized in Table \ref{tab:limits}.
These values can be used for testing other methods of calculating these numbers and for devising a closed formula, if ever possible.
However, a single number does not tell us much about the type of semigroups.

\subsection{Size Distributions}
\begin{figure}
\begin{center}
\input{tikz/T4size6peaks.tikz}
\end{center}
\caption{The six peaks of $\mathcal T_4$. The main bulk of the size distribution of transformation semigroups of degree 4.}
\label{fig:T4size6peaks}
\end{figure}
It is a basic fact of group theory (Lagrange's Theorem) that the subgroups of a group $G$ have orders that are divisors of $|G|$.
Therefore, the size of a permutation group of degree $n$ should be a divisor of $n!$, yielding a size distribution of these permutation groups with spikes at these values (how many groups for a divisor is a nontrivial matter).
For transformation semigroups we do not have this restriction, but still, the continuous looking curve for the size distribution of $\mathbf{Sub}_{\mathcal S_4}(\mathcal T_4)$ is somewhat surprising, see Fig.~\ref{fig:T4size6peaks}.

\begin{figure}
\begin{center}
\input{tikz/P_T4_sizes.tikz}
\end{center}
\caption{The double distribution of transformation semigroups of degree 4 containing nontrivial permutations. Semigroups of even order are more abundant.}
\label{fig:PT4sizes}
\end{figure}

The next question is whether the size distribution is more `group-like' for semigroups containing nontrivial permutations.

Figure \ref{fig:PT4sizes} shows that the curve is again continuous looking. 
Moreover, it has a curious even-odd alternating pattern, actually drawing two curves. 
The pattern is mainly due to the semigroups containing only one nontrivial permutation (93.93\% of semigroups). 


\subsection{Semigroup Structure Summary Heatmaps}

When studying a semigroup, it is a standard first step to ask about its structure in terms of its Green's equivalence relations \cite{clifford_preston,Howie95,QBook}. These can be defined 
 in terms of divisibility relations
$$ t\ \mathcal R\ s \iff \exists p,q\in S^1 \text{ such that } t=sp \text{ and } s=tq,$$
$$ t\ \mathcal L\ s \iff \exists p,q\in S^1 \text{ such that } t=ps \text{ and } s=qt,$$
$$ t\ \mathcal J\ s \iff \exists p,q,u,v\in S^1 \text{ such that } t=psq \text{ and } s=utv.$$
The $\mathcal D$ relation is defined to be the composition of the $\mathcal L$ and $\mathcal R$ relations (in either order); so $t \mathcal D s$ if and only if $t\mathcal L u \mathcal R s$ for some $u\in S$.  For finite semigroups, the $\mathcal D$ relation coincides with the $\mathcal J$ relation.  Since semigroup elements are $\mathcal D$-related precisely when they can be obtained from each other by multiplication within the semigroup, the $\mathcal D$-classes can be thought of as the `local pools of reversibility'.


\subsubsection{Size versus the number of $\mathcal D$-classes}

\begin{figure}
\input{tikz/I3SvsD.tikz}
\caption{Size versus the number of $\mathcal D$-classes for partial permutation semigroups up to degree 3.}
\label{fig:I3SvsD}
\end{figure}

\begin{figure}
\input{tikz/T4_SvsD.tikz}
\caption{Size versus the number of $\mathcal D$-classes for transformation semigroups up to degree 4. Frequency values in millions.}
\label{fig:T4SvsD}
\end{figure}

Each $\mathcal D$-class of a finite semigroup contains elements that are mutually reachable from each other by left or right multiplication. 
Is there a relation between the number of elements and the number of $\mathcal D$-classes beyond the trivial constraint that the former is an upper bound for the latter?
Visualising the relationship as a heatmap of all degree 3 inverse semigroups (Fig.~\ref{fig:I3SvsD}) we see that for many of them the $\mathcal D$-classes are singletons. Also, the heatmap is discontinuous, which is probably explained by the fact that inverse semigroups, consisting of partial permutations,  are the closest to groups.
In contrast, the analogous heatmap for $\mathbf{Sub}_{\mathcal S_4}(\mathcal T_4)$ (Fig.~\ref{fig:T4SvsD}) looks in a sense continuous (up to about 155).


\subsubsection{Size versus the number of idempotents}

\begin{figure}
\input{tikz/PT3SvsI.tikz}
\caption{Size versus the number of idempotents for partial transformation semigroups up to degree 3.}
\label{fig:PT3SvsI}
\end{figure}

\begin{figure}
\input{tikz/T4_SvsI.tikz}
\caption{Size versus the number of idempotents for transformation semigroups up to degree 4. Frequency values in millions.}
\label{fig:T4SvsI}
\end{figure}

Idempotents, which satisfy $x=x^2$, also play an important role in the analysis of semigroup structure since they are the identities of the subgroups of a semigroup. Figures \ref{fig:PT3SvsI} and \ref{fig:T4SvsI} show connection between the size of the semigroup and the number of idempotents. The heatmaps indicate that most of the semigroups are clustered on a line.

\subsection{Superfractals in the Temperley-Lieb Monoid}

\begin{figure}
\begin{center}
\includegraphics[width=.75\textwidth]{J16_6.png}
\end{center}
\caption{The positions  of idempotents in the sixth $\mathcal D$-class of $\text{TL}_{16}$. }
\label{fig:ferns}
\end{figure}

 Looking into the structure of the individual $\mathcal D$-classes we often draw the so called `eggbox' picture
\cite{clifford_preston,Howie95}. 
The Temperley-Lieb monoid has a single hierarchy of $\mathcal D$-classes determined by the number of cups and caps in the planar diagram.
However, the locations of the idempotents have an interesting structure (assuming the standard generating set), see Figure \ref{fig:ferns}. The picture looks like a superfractal \cite{barnsley2006superfractals}, but we do not know the generating iterated function systems.

\section{Open Problems}
The generated data sets are awash with interesting observations and open questions (including some not explicitly referred above). Here we just mention a few. 
\begin{enumerate}
\item Why are there six peaks in the distribution of sizes in $\mathbf{Sub}_{\mathcal S_4}(\mathcal T_4)$? (see Fig.~\ref{fig:T4size6peaks}) Why are semigroups of size 60 the most abundant? Is there a number theoretical or algebraic explanation? What is the shape for $\mathcal T_5$ and beyond?
\item What is the asymptotic behaviour of the ratio of subsemigroups  and  subsets of the diagram semigroups?
\item Is there a convergence in the shape of the distributions? Do they become single-peaked as the degree increases? If so, that would imply that we can talk about typical members of degree $n$ diagram semigroups in a statistical sense.
\item Explain the fractal structure appearing in $\text{TL}_n$.
\end{enumerate}




