Geodesic
Reflection positivity, rank connectivity, and homomorphism of graphs
Freedman, Michael1 ; Lovász, László2 ; Schrijver, Alexander3
1 Microsoft Institute for Quantum Physics, Santa Barbara, California 93106
2 Microsoft Research, One Microsoft Way, Redmond, Washington 98052
3 CWI, Kruislaan 413, 1098 SJ Amsterdam, The Netherlands
Journal of the American Mathematical Society, Tome 20 (2007) no. 1, pp. 37-51

Voir la notice de l'article provenant de la source American Mathematical Society

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.
DOI : 10.1090/S0894-0347-06-00529-7

Freedman, Michael 1 ; Lovász, László 2 ; Schrijver, Alexander 3

1 Microsoft Institute for Quantum Physics, Santa Barbara, California 93106
2 Microsoft Research, One Microsoft Way, Redmond, Washington 98052
3 CWI, Kruislaan 413, 1098 SJ Amsterdam, The Netherlands 
@article{10_1090_S0894_0347_06_00529_7,
     author = {Freedman, Michael and Lov\~A{\textexclamdown}sz, L\~A{\textexclamdown}szl\~A{\textthreesuperior} and Schrijver, Alexander},
     title = {Reflection positivity, rank connectivity, and homomorphism of graphs},
     journal = {Journal of the American Mathematical Society},
     pages = {37--51},
     publisher = {mathdoc},
     volume = {20},
     number = {1},
     year = {2007},
     doi = {10.1090/S0894-0347-06-00529-7},
     url = {http://geodesic.mathdoc.fr/articles/10.1090/S0894-0347-06-00529-7/}
}
TY  - JOUR
AU  - Freedman, Michael
AU  - Lovász, László
AU  - Schrijver, Alexander
TI  - Reflection positivity, rank connectivity, and homomorphism of graphs
JO  - Journal of the American Mathematical Society
PY  - 2007
SP  - 37
EP  - 51
VL  - 20
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.1090/S0894-0347-06-00529-7/
DO  - 10.1090/S0894-0347-06-00529-7
ID  - 10_1090_S0894_0347_06_00529_7
ER  - 
%0 Journal Article
%A Freedman, Michael
%A Lovász, László
%A Schrijver, Alexander
%T Reflection positivity, rank connectivity, and homomorphism of graphs
%J Journal of the American Mathematical Society
%D 2007
%P 37-51
%V 20
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.1090/S0894-0347-06-00529-7/
%R 10.1090/S0894-0347-06-00529-7
%F 10_1090_S0894_0347_06_00529_7
Freedman, Michael; Lovász, László; Schrijver, Alexander. Reflection positivity, rank connectivity, and homomorphism of graphs. Journal of the American Mathematical Society, Tome 20 (2007) no. 1, pp. 37-51. doi: 10.1090/S0894-0347-06-00529-7

[1] Berg, Christian, Christensen, Jens Peter Reus, Ressel, Paul Positive definite functions on abelian semigroups Math. Ann. 1976 253 274

[2] Berg, Christian, Christensen, Jens Peter Reus, Ressel, Paul Harmonic analysis on semigroups 1984

[3] Berg, Christian, Maserick, P. H. Exponentially bounded positive definite functions Illinois J. Math. 1984 162 179

[4] De La Harpe, P., Jones, V. F. R. Graph invariants related to statistical mechanical models: examples and problems J. Combin. Theory Ser. B 1993 207 227

[5] Lindahl, R. J., Maserick, P. H. Positive-definite functions on involution semigroups Duke Math. J. 1971 771 782

[6] Welsh, D. J. A. Complexity: knots, colourings and counting 1993

[7] Whitney, Hassler The coloring of graphs Ann. of Math. (2) 1932 688 718

Cité par Sources :