Reflection positivity, rank connectivity, and homomorphism of graphs
HTML articles powered by AMS MathViewer
- by Michael Freedman, László Lovász and Alexander Schrijver;
- J. Amer. Math. Soc. 20 (2007), 37-51
- DOI: https://doi.org/10.1090/S0894-0347-06-00529-7
- Published electronically: April 13, 2006
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
- 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 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, DOI 10.1007/978-1-4612-1128-0
- 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 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, DOI 10.1215/S0012-7094-71-03893-2 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, DOI 10.1017/CBO9780511752506
- Hassler Whitney, The coloring of graphs, Ann. of Math. (2) 33 (1932), no. 4, 688–718. MR 1503085, DOI 10.2307/1968214
Bibliographic 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
- Received by editor(s): July 28, 2004
- Published electronically: April 13, 2006
- © Copyright 2006 by M. Freedman, L. Lovasz, and A. 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
- MathSciNet review: 2257396