Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Journal of the American Mathematical Society
Journal of the American Mathematical Society
ISSN 1088-6834(online) ISSN 0894-0347(print)

 

Reflection positivity, rank connectivity, and homomorphism of graphs


Authors: Michael Freedman, László Lovász and Alexander Schrijver
Journal: J. Amer. Math. Soc. 20 (2007), 37-51
MSC (2000): Primary 05C99; Secondary 82B99
Published electronically: April 13, 2006
MathSciNet review: 2257396
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: It is shown that a graph parameter can be realized as the number of homomorphisms into a fixed (weighted) graph if and only if it satisfies two linear algebraic conditions: reflection positivity and exponential rank connectivity. In terms of statistical physics, this can be viewed as a characterization of partition functions of vertex coloring models.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Journal of the American Mathematical Society with MSC (2000): 05C99, 82B99

Retrieve articles in all journals with MSC (2000): 05C99, 82B99


Additional Information

Michael Freedman
Affiliation: Microsoft Institute for Quantum Physics, Santa Barbara, California 93106

László Lovász
Affiliation: Microsoft Research, One Microsoft Way, Redmond, Washington 98052

Alexander Schrijver
Affiliation: CWI, Kruislaan 413, 1098 SJ Amsterdam, The Netherlands

DOI: http://dx.doi.org/10.1090/S0894-0347-06-00529-7
PII: S 0894-0347(06)00529-7
Keywords: Graph homomorphism, partition function, connection matrix
Received by editor(s): July 28, 2004
Published electronically: April 13, 2006
Article copyright: © Copyright 2006 by M. Freedman, L. Lovasz, and A. Schrijver