Borgs, C. and Chayes, J. T. and Lovász, László and T. Sós, Vera and Vesztergombi, Katalin (2012) Convergent sequences of dense graphs II. Multiway cuts and statistical physics. ANNALS OF MATHEMATICS, 176 (1). pp. 151219. ISSN 0003486X

Text
10.1.1.116.302.pdf Download (554kB)  Preview 
Abstract
We consider sequences of graphs (Gn) and define various notions of convergence related to these sequences including "leftconvergence," defined in terms of the densities of homomorphisms from small graphs into G n, and "rightconvergence," defined in terms of the densities of homomorphisms from G n into small graphs. We show that rightconvergence is equivalent to leftconvergence, 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.
Item Type:  Article 

Uncontrolled Keywords:  QUASIRANDOM GRAPHS; 
Subjects:  Q Science / természettudomány > QA Mathematics / matematika Q Science / természettudomány > QA Mathematics / matematika > QA166QA166.245 Graphs theory / gráfelmélet 
SWORD Depositor:  MTMT SWORD 
Depositing User:  MTMT SWORD 
Date Deposited:  29 Jun 2020 14:19 
Last Modified:  29 Jun 2020 14:19 
URI:  http://real.mtak.hu/id/eprint/110729 
Actions (login required)
Edit Item 