Remote Access Journal of the American Mathematical Society
Green Open Access

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

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