Edge-reflection positivity and weighted graph homomorphisms

B. Szegedy (2007) [12] showed that the number of homomorphisms into a weighted graph is equal to the partition function of a complex edge-coloring model. Using some results in geometric invariant theory, we characterize for which weighted graphs the edge-coloring model can be taken to be real-valued that is, we characterize for which weighted graphs the number of homomorphisms into them is edge-reflection positive. In particular, we determine explicitly for which simple graphs the number of homomorphisms into them is equal to the partition function of a real edge-coloring model. This answers a question posed by Szegedy.