Edge-reflection positivity and weighted graph homomorphisms

JOURNAL OF COMBINATORIAL THEORY SERIES A

卷:129

Article

Regts, Guus^1,2 

[1] Univ Amsterdam, NL-1012 WX Amsterdam, Netherlands

[2] CWI, NL-1009 AB Amsterdam, Netherlands

关键词: Graph homomorphism;    Edge-coloring model;    Edge-reflection positivity;    Graph invariant;    Partition function;    Vertex model;   

DOI  :  10.1016/j.jcta.2014.09.006

来源: Elsevier

【 摘 要 】

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. (C) 2014 Elsevier Inc. All rights reserved.

【 授权许可】

Free