A monoid is, for me, a set of mappings on a finite domain which is closed under composition and contains the identity mapping. The composition is, of course, associative. Thus, it is “a group without the inverses”.
A homomorphism from a graph X to a graph Y is a map from vertices of X to Y which maps edges to edges. We don’t care what it does not non-edges: they may map to non-edges, or to edges, or collapse to single vertices. An endomorphism of a graph X is a homomorphism from X to itself. As a special instance of a general principle, the endomorphisms of a given graph form a monoid: the identity map is certainly an endomorphism, and the composition of endomorphisms is an endomorphism.
Anyone who has heard me banging on about synchronization recently will know that I think that endomorphism monoids contain the key. A monoid fails to be synchronizing (that is, fails to contain a map which collapses everything to a single point) if and only if it is contained in the endomorphism monoid of a graph. Moreover, we can take the graph to have clique number equal to chromatic number; so the graphs which occur are rather special.
So it is worth asking, what do the endomorphism monoids of these special graphs look like? The answer can be a bit of a surprise sometimes.
Here I want to discuss just one example. The graph X is the n×n grid. (This is not in the sense of lattices and statistical mechanics. The vertices are the cells of an n×n array, and two vertices are joined if they lie in the same row or column. So any row or column is a complete graph of size n.)
There are just two kinds of endomorphisms of this graph:
- automorphisms, that is, endomorphisms which happen to be permutations, and map non-edges always to non-edges);
- endomorphisms which collapse the whole graph onto one row or column.
The first type are easy to understand. We can permute the rows of the grid, and permute the columns (independent of what we did to the rows); and we may if we wish transpose the grid, interchanging rows and columns. The group of automorphisms is what is known as the wreath product of the symmetric group of degree n with the cyclic group of order 2, in its product action. Its order is 2(n!)^{2}.
The second type are “essentially” Latin squares. Suppose we map to the first row, whose vertices are numbered from 1 to n. Since there are n^{2} vertices altogether, and at most n can collapse onto any given vertex, each vertex in the row is the image of n vertices in the grid. We can fill in the array by putting into each cell the number of the vertex in the first row where it is mapped. Now two vertices mapping to the same place must be non-adjacent, so not in the same row or column. This means that our array has each of the numbers 1 to n exactly once in each row, and once in each column.
We call two Latin squares equivalent if one can be transformed into the other by permuting rows and columns, possibly transposing, and permuting the entries. Now if f is an endomorphism of the type just discussed, and g is an automorphism, then gf (meaning g first, then f) corresponds to the Latin square where we permute the rows and columns and possibly transpose. Also, if h is any endomorphism, then fh corresponds to the same Latin square with the symbols permuted (and the image may be a different row or column, but that doesn’t affect the Latin square.)
So the non-automorphisms in the monoid generated by f and G correspond to an equivalence class of Latin squares.
One’s first reaction to this should be delight. We have put an algebraic structure (a monoid) on the Latin squares; this should certainly tell us something interesting! Unfortunately, the structure of the monoid is rather boring. Suppose that L_{1}, L_{2}, …, L_{r} are representatives of all the equivalence classes of Latin squares of order n. For each i, we let S_{i} be the set of endomorphisms corresponding to squares equivalent to L_{i}. If G is the automorphism group, then each set S_{i}∪G is a submonoid. Also, the set S_{i} is closed under composition, so is itself a semigroup. Moreover, the product of S_{i} and S_{j} is S_{i}. So the composition, “coarsened” by thinking of each S_{i} as a single element, is the rather trivial one: the product of any sequence of elements is just the first one in the sequence.
Here is a picture of the monoid.
We can see more from this.
First, the number of inequivalent Latin squares of order n is huge, not far short of n^{n2}. So the endomorphism monoid of the grid graph is vast, and the automorphisms form only a small part of it.
Second, the union of any collection of the S_{i} is itself a semigroup. So the number of subsemigroups is huge, exponentially large in terms of the order of the monoid itself. This is in contrast to what happens for groups, where a group of order n can have at most n^{log n} subgroups.
It is not quite clear what the existence of monsters like this has to say about synchronizing monoids …
By contrast, let Y be the complement of the graph X. We have the same two types of endomorphisms of Y. But those which are not automorphisms collapse the graph along rows or along columns onto a “transversal” set, a set containing one element from each row and one from each column. Since there is only one kind of transversal set, up to automorphisms of the graph, the picture of the endomorphism monoid differs from the picture for X in that there is only one semigroup S_{i} rather than a vast horde of them.
There are a lot of interesting questions inspired by all this!