Convergent sequences of dense graphs II. Multiway cuts and statistical physics
成果类型：
Article
署名作者：
Borgs, C.; Chayes, J. T.; Lovasz, L.; Sos, V. T.; Vesztergombi, K.
刊物名称：
ANNALS OF MATHEMATICS
ISSN/ISSBN：
0003-486X
DOI：
10.4007/annals.2012.176.1.2
发表日期：
2012
页码：
151-219
关键词：
摘要：
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 Szemeredi 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.