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
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.
- 1. Christian Berg, Jens Peter Reus Christensen, and Paul Ressel, Positive definite functions on abelian semigroups, Math. Ann. 223 (1976), no. 3, 253–274. MR 0420150, https://doi.org/10.1007/BF01360957
- 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, J. Combin. Theory Ser. B 57 (1993), no. 2, 207–227. MR 1207488, https://doi.org/10.1006/jctb.1993.1017
- 6. R. J. Lindahl and P. H. Maserick, Positive-definite functions on involution semigroups, Duke Math. J. 38 (1971), 771–782. MR 0291826
- 7. 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
- 8. B. Szegedy: Edge coloring models and reflection positivity (manuscript), http://arxiv.org/abs/math.CO/0505035
- 9. D. J. A. Welsh, Complexity: knots, colourings and counting, London Mathematical Society Lecture Note Series, vol. 186, Cambridge University Press, Cambridge, 1993. MR 1245272
- 10. Hassler Whitney, The coloring of graphs, Ann. of Math. (2) 33 (1932), no. 4, 688–718. MR 1503085, 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
DOI:
https://doi.org/10.1090/S0894-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
