Endomorphism monoids of graphs

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 n2 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 L1, L2, …, Lr are representatives of all the equivalence classes of Latin squares of order n. For each i, we let Si be the set of endomorphisms corresponding to squares equivalent to Li. If G is the automorphism group, then each set SiG is a submonoid. Also, the set Si is closed under composition, so is itself a semigroup. Moreover, the product of Si and Sj is Si. So the composition, “coarsened” by thinking of each Si 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.

A monoid

We can see more from this.

First, the number of inequivalent Latin squares of order n is huge, not far short of nn2. 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 Si 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 nlog 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 Si rather than a vast horde of them.

There are a lot of interesting questions inspired by all this!

Advertisements

About Peter Cameron

I count all the things that need to be counted.
This entry was posted in exposition, open problems and tagged , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s