Geodesic
Convergent sequences of dense graphs II. Multiway cuts and statistical physics
Christian Borgs1 ; Jennifer T. Chayes1 ; László Lovász 2 ; Vera T. Sós 3 ; Katalin Vesztergombi2
1 Microsoft Research, 1 Memorial Drive, Cambridge, MA 02142
2 Department of Computer Science, Eötvös Loránd University, H-1518 Budapest, Hungary
3 Alfréd Rényi, Institute of Mathematics, Hungarian Academy of Sciences, H-1364 Budapest, Hungary
Annals of mathematics, Tome 176 (2012) no. 1, pp. 151-219

Voir la notice de l'article provenant de la source Annals of Mathematics website

We consider sequences of graphs $(G_n)$ and define various notions of convergence related to these sequences including “left-convergence,” defined in terms of the densities of homomorphisms from small graphs into $G_n$, and “right-convergence,” defined in terms of the densities of homomorphisms from $G_n$ into small graphs.
We show that right-convergence is equivalent to left-convergence, both for simple graphs $G_n$, and for graphs $G_n$ with nontrivial nodeweights and edgeweights. Other equivalent conditions for convergence are given in terms of fundamental notions from combinatorics, such as maximum cuts and Szemerédi partitions, and fundamental notions from statistical physics, like energies and free energies. We thereby relate local and global properties of graph sequences. Quantitative forms of these results express the relationships among different measures of similarity of large graphs.

DOI : 10.4007/annals.2012.176.1.2

Christian Borgs 1 ; Jennifer T. Chayes 1 ; László Lovász  2 ; Vera T. Sós  3 ; Katalin Vesztergombi 2

1 Microsoft Research, 1 Memorial Drive, Cambridge, MA 02142
2 Department of Computer Science, Eötvös Loránd University, H-1518 Budapest, Hungary
3 Alfréd Rényi, Institute of Mathematics, Hungarian Academy of Sciences, H-1364 Budapest, Hungary 
@article{10_4007_annals_2012_176_1_2,
     author = {Christian Borgs and Jennifer T.  Chayes and L\'aszl\'o Lov\'asz  and Vera T. S\'os  and Katalin Vesztergombi},
     title = {Convergent sequences of dense graphs {II.}  {Multiway} cuts and statistical physics},
     journal = {Annals of mathematics},
     pages = {151--219},
     publisher = {mathdoc},
     volume = {176},
     number = {1},
     year = {2012},
     doi = {10.4007/annals.2012.176.1.2},
     mrnumber = {2925382},
     zbl = {1247.05124},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.4007/annals.2012.176.1.2/}
}
TY  - JOUR
AU  - Christian Borgs
AU  - Jennifer T.  Chayes
AU  - László Lovász 
AU  - Vera T. Sós 
AU  - Katalin Vesztergombi
TI  - Convergent sequences of dense graphs II.  Multiway cuts and statistical physics
JO  - Annals of mathematics
PY  - 2012
SP  - 151
EP  - 219
VL  - 176
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.4007/annals.2012.176.1.2/
DO  - 10.4007/annals.2012.176.1.2
LA  - en
ID  - 10_4007_annals_2012_176_1_2
ER  - 
%0 Journal Article
%A Christian Borgs
%A Jennifer T.  Chayes
%A László Lovász 
%A Vera T. Sós 
%A Katalin Vesztergombi
%T Convergent sequences of dense graphs II.  Multiway cuts and statistical physics
%J Annals of mathematics
%D 2012
%P 151-219
%V 176
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.4007/annals.2012.176.1.2/
%R 10.4007/annals.2012.176.1.2
%G en
%F 10_4007_annals_2012_176_1_2
Christian Borgs; Jennifer T.  Chayes; László Lovász ; Vera T. Sós ; Katalin Vesztergombi. Convergent sequences of dense graphs II.  Multiway cuts and statistical physics. Annals of mathematics, Tome 176 (2012) no. 1, pp. 151-219. doi: 10.4007/annals.2012.176.1.2

Cité par Sources :