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

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?)

  • 1. C. Berg, J.P.R. Christensen, P. Ressel: Positive definite functions on abelian semigroups, Mathematische Annalen 223 (1976), 253-272. MR 0420150 (54:8165)
  • 2. C. Berg, J.P.R. Christensen, P. Ressel: Harmonic Analysis on Semigroups--Theory of Positive Definite and Related Functions, Graduate Texts in Mathematics 100, Springer, New York, 1984. MR 0747302 (86b:43001)
  • 3. C. Berg and P.H. Maserick: Exponentially bounded positive definite functions, Illinois Journal of Mathematics 28 (1984), 162-179.MR 0730718 (85i:43012)
  • 4. M. Freedman, L. Lovász and D. Welsh (unpublished).
  • 5. P. de la Harpe and V.F.R. Jones: Graph Invariants Related to Statistical Mechanical Models: Examples and Problems, Journal of Combinatorial Theory B 57 (1993), 207-227. MR 1207488 (94c:05033)
  • 6. R.J. Lindahl and P.H. Maserick: Positive-definite functions on involution semigroups, Duke Mathematical Journal 38 (1971), 771-782.MR 0291826 (45:916)
  • 7. L. Lovász, B. Szegedy: Limits of graph sequences, Microsoft Research Technical Report MSR-TR-2004-79,
  • 8. B. Szegedy: Edge coloring models and reflection positivity (manuscript),
  • 9. D.J.A. Welsh: Complexity: Knots, Colourings and Counting, London Math. Soc. Lecture Note Series 186, Cambridge University Press, Cambridge, 1993. MR 1245272 (94m:57027)
  • 10. H. Whitney: The coloring of graphs, Ann. of Math. 33 (1932), 688-718.MR 1503085

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

American Mathematical Society