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 H1 and H2 be graphs. Suppose that, for every graph G, we have hom(G,H1) = hom(G,H2). Then H1 is isomorphic to H2.
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,H1) = hom(G,H2) for all graphs G, then inj(G,H1) = inj(G,H2) for all graphs G. In particular, taking G = H1, we see that (since there is at least one injection from H1 to itself, namely the identity map) there is at least one injection from H1 to H2. Similarly there is an injective homomorphism from H2 to H1. 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 H1 and H2 be graphs which have no automorphism of order p. Suppose that, for every graph G, we have hom(G,H1) ≡ hom(G,H2) (mod p). Then H1 is isomorphic to H2.
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,H1) ≡ inj(G,N2) (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 H1 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 H1 to H2 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 H1 and H2 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.