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
DOI:
https://doi.org/10.1090/S0894-0347-06-00529-7
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.
- Christian Berg, Jens Peter Reus Christensen, and Paul Ressel, Positive definite functions on abelian semigroups, Math. Ann. 223 (1976), no. 3, 253–274. MR 420150, DOI https://doi.org/10.1007/BF01360957
- Christian Berg, Jens Peter Reus Christensen, and Paul Ressel, Harmonic analysis on semigroups, Graduate Texts in Mathematics, vol. 100, Springer-Verlag, New York, 1984. Theory of positive definite and related functions. MR 747302
- Christian Berg and P. H. Maserick, Exponentially bounded positive definite functions, Illinois J. Math. 28 (1984), no. 1, 162–179. MR 730718 FLW M. Freedman, L. Lovász and D. Welsh (unpublished).
- P. de la Harpe and V. F. R. Jones, Graph invariants related to statistical mechanical models: examples and problems, J. Combin. Theory Ser. B 57 (1993), no. 2, 207–227. MR 1207488, DOI https://doi.org/10.1006/jctb.1993.1017
- R. J. Lindahl and P. H. Maserick, Positive-definite functions on involution semigroups, Duke Math. J. 38 (1971), 771–782. MR 291826 LSz L. Lovász, B. Szegedy: Limits of graph sequences, Microsoft Research Technical Report MSR-TR-2004-79, ftp://ftp.research.microsoft.com/pub/tr/TR-2004-79.pdf SZ B. Szegedy: Edge coloring models and reflection positivity (manuscript), http://arxiv.org/abs/math.CO/0505035
- D. J. A. Welsh, Complexity: knots, colourings and counting, London Mathematical Society Lecture Note Series, vol. 186, Cambridge University Press, Cambridge, 1993. MR 1245272
- Hassler Whitney, The coloring of graphs, Ann. of Math. (2) 33 (1932), no. 4, 688–718. MR 1503085, DOI https://doi.org/10.2307/1968214
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
