Two of my colleagues have been doing interesting things with counting homomorphisms modulo a prime; Thomas Müller with group homomorphisms, and Mark Jerrum with graph homomorphisms. I may get round to discussing Thomas’s work later. Here I want to discuss a simple but very pretty result of John Faben and Mark Jerrum, which Mark told us about last Friday.

In what follows, graphs are allowed to have loops but not multiple edges; they are undirected.

The problem is as follows. Given a (finite) graph, and a prime number *p*, we are allowed to reduce the graph in the following way. If it has an automorphism of prime order, then delete all vertices moved by this automorphism, and all edges attached to them, leaving only the fixed vertices and edges. If the new graph has an automorphism of order *p*, repeat the procedure, and so on until the resulting graph has no automorphism of order *p*. This reduction can be done in many different ways, and of course new automorphisms can arise during the process that were not automorphisms of the original graph. So it seems more than a little surprising that, up to isomorphism, the graph obtained “at the end of the line” is unique, independent of the reduction process.

The proof uses the Lovász technology for graph homomorphisms. At the foundation of the theory is the following result. A *graph homomorphism* is a map from the vertex set of one graph to another which maps edges to edges. We let hom(*G,H*) denote the number of homomorphisms from *G* to *H*.

Let *H*_{1} and *H*_{2} be graphs. Suppose that, for every graph *G*, we have hom(*G,H*_{1}) = hom(*G,H*_{2}). Then *H*_{1} is isomorphic to *H*_{2}.

The proof uses the auxiliary function inj(*G,H*), the number of injective homomorphisms from *G* to *H*. Now, just as with algebraic homomorphisms, any graph homomorphism can be written as the composition of a quotient map and an injective homomorphism. Using this and a simple induction, it is easy to see that, if hom(*G,H*_{1}) = hom(*G,H*_{2}) for all graphs *G*, then inj(*G,H*_{1}) = inj(*G,H*_{2}) for all graphs *G*. In particular, taking *G* = *H*_{1}, we see that (since there is at least one injection from *H*_{1} to itself, namely the identity map) there is at least one injection from *H*_{1} to *H*_{2}. Similarly there is an injective homomorphism from *H*_{2} to *H*_{1}. It follows that the injections in both directions are isomorphisms (since an injective homomorphism cannot decrease the number of edges).

Faben’s and Jerrum’s variant is:

Let *H*_{1} and *H*_{2} be graphs which have no automorphism of order *p*. Suppose that, for every graph *G*, we have hom(*G,H*_{1}) ≡ hom(*G,H*_{2}) (mod *p*). Then *H*_{1} is isomorphic to *H*_{2}.

The proof is a modification of the one just given. The same induction argument shows that, with the given hypothesis, we also have inj(*G,H*_{1}) ≡ inj(*G,N*_{2}) (mod *p*). Now an injective homomorphism from a graph to itself is an automorphism. By hypothesis, and the theorem of Cauchy, the number of automorphisms of *H*_{1} is not congruent to 0 (mod *p*); for, if it were, then Cauchy’s theorem would give the existence of an automorphism of order *p*, contrary to assumption. So the number of injective homomorphisms from *H*_{1} to *H*_{2} is also non-zero (mod *p*), and in particular is non-zero. Then the proof continues as before.

To complete the proof of the original assertion, we note that, if *H* is any graph, and *H** the graph obtained by one step of the reduction (removing the vertices moved by an automorphism of order *p*), then hom(*G,H*) ≡ hom(*G,H**) (mod *p*). For the homomorphisms from *G* to *H* which are fixed by the automorphism are precisely those which map *G* to *H**. Hence, if *H*_{1} and *H*_{2} are two graphs obtained from *H* by continuing the reduction process until it terminates, then the hypotheses of the theorem are satisfied by these two graphs, and so they are isomorphic.

I was going to ask a mathoverflow question related to this, but I figured it’s best to ask here.

If we were to make an analogy with the p-cores of partitions, we can call the resulting graph after eliminating vertices moved by automorphisms of order p, the p-core of the graph. Is there a meaningful “p-quotient”? Can we talk of a natural bijection between graphs and their p-core plus an additional gadget?

Thanks!

That’s a nice question! Off the top of my head I can’t see what such a gadget would look like. Does anyone reading this have any good ideas?