Homomorphisms of Strongly Regular Graphs

We prove that if G and H are primitive strongly regular graphs with the same parameters and φ is a homomorphism from G to H, then φ is either an isomorphism or a coloring (homomorphism to a complete subgraph). Moreover, any such coloring is optimal for G and its image is a maximum clique of H. Therefore, the only endomorphisms of a primitive strongly regular graph are automorphisms or colorings. This confirms and strengthens a conjecture of Peter Cameron and Priscila Kazanidis that all strongly regular graphs are cores or have complete cores. The proof of the result is elementary, mainly relying on linear algebraic techniques. In the second half of the paper we discuss the idea underlying the proof, namely that it can be seen as a straightforward application of complementary slackness to a dual pair of semidefinite programs that define the Lovász theta function. We also consider implications of the result and show that essentially the same proof can be used to obtain a more general statement. We believe that one of the main contributions of the work is the novel proof technique, which is the first able to make use of the combinatorial regularity of a graph in order to obtain results about its endomorphisms/homomorphisms. Thus we expect this approach to have further applicability to the study of homomorphisms of highly regular graphs.