|
Reflection positivity, rank connectivity, and homomorphism of graphs
Author(s):
Michael
Freedman;
László
Lovász;
Alexander
Schrijver
Journal:
J. Amer. Math. Soc.
20
(2007),
37-51.
MSC (2000):
Primary 05C99;
Secondary 82B99
Posted:
April 13, 2006
MathSciNet review:
2257396
Retrieve article in:
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:
-
- 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, 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 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
DOI:
10.1090/S0894-0347-06-00529-7
PII:
S 0894-0347(06)00529-7
Keywords:
Graph homomorphism,
partition function,
connection matrix
Received by editor(s):
July 28, 2004
Posted:
April 13, 2006
Copyright of article:
Copyright
2006,
by M. Freedman, L. Lovasz, and A. Schrijver
|
