Left and right convergence of graphs with bounded degree

The theory of convergent graph sequences has been worked out in two extreme cases, dense graphs and bounded degree graphs. One can define convergence in terms of counting homomorphisms from fixed graphs into members of the sequence (left‐convergence), or counting homomorphisms into fixed graphs (rig...

Full description

Saved in:
Bibliographic Details
Published in:Random structures & algorithms 2013-01, Vol.42 (1), p.1-28
Main Authors: Borgs, Christian, Chayes, Jennifer, Kahn, Jeff, Lovász, László
Format: Article
Language:English
Subjects:
cluster expansion
Dobrushin Uniqueness
graph limits
left convergence
right convergence
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by cdi_FETCH-LOGICAL-c3354-ae18d3af6109d2ace27a017860099c497c02c995b4b76f43b137637073332c183
cites cdi_FETCH-LOGICAL-c3354-ae18d3af6109d2ace27a017860099c497c02c995b4b76f43b137637073332c183
container_end_page 28
container_issue 1
container_start_page 1
container_title Random structures & algorithms
container_volume 42
creator Borgs, Christian
Chayes, Jennifer
Kahn, Jeff
Lovász, László
description The theory of convergent graph sequences has been worked out in two extreme cases, dense graphs and bounded degree graphs. One can define convergence in terms of counting homomorphisms from fixed graphs into members of the sequence (left‐convergence), or counting homomorphisms into fixed graphs (right‐convergence). Under appropriate conditions, these two ways of defining convergence was proved to be equivalent in the dense case by Borgs, Chayes, Lovász, Sós and Vesztergombi. In this paper a similar equivalence is established in the bounded degree case, if the set of graphs in the definition of right‐convergence is appropriately restricted. In terms of statistical physics, the implication that left convergence implies right convergence means that for a left‐convergent sequence, partition functions of a large class of statistical physics models converge. The proof relies on techniques from statistical physics, like cluster expansion and Dobrushin Uniqueness. © 2012 Wiley Periodicals, Inc. Random Struct. 2012
doi_str_mv 10.1002/rsa.20414
format article
fullrecord <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_journals_1176933285</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>2820267241</sourcerecordid><originalsourceid>FETCH-LOGICAL-c3354-ae18d3af6109d2ace27a017860099c497c02c995b4b76f43b137637073332c183</originalsourceid><addsrcrecordid>eNp1kD1PwzAQhi0EEqUw8A8sMTGk9Vdie6wKFFAFEgUhsViOc0lTSlLslNJ_T0qAjelueJ67Vy9Cp5QMKCFs6IMdMCKo2EM9SrSKmKBqf7cLFmnF2SE6CmFBCJGc8R5SU8gbbKsM-7KYN9jV1Qf4AioHuM5x4e1qHvCmbOY4rddVBhnOoPAAx-ggt8sAJz-zj56uLh_H19H0fnIzHk0jx3ksIgtUZdzmSRsmY9YBk5ZQqRJCtHZCS0eY0zpORSqTXPCUcplw2abjnDmqeB-ddXdXvn5fQ2jMol77qn1pKJWJbjEVt9R5Rzlfh-AhNytfvlm_NZSYXTGmLcZ8F9Oyw47dlEvY_g-ah9no14g6owwNfP4Z1r-aRHIZm-e7iSG3kumXC2Fm_AtZJ3DA</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>1176933285</pqid></control><display><type>article</type><title>Left and right convergence of graphs with bounded degree</title><source>Wiley-Blackwell Read &amp; Publish Collection</source><creator>Borgs, Christian ; Chayes, Jennifer ; Kahn, Jeff ; Lovász, László</creator><creatorcontrib>Borgs, Christian ; Chayes, Jennifer ; Kahn, Jeff ; Lovász, László</creatorcontrib><description>The theory of convergent graph sequences has been worked out in two extreme cases, dense graphs and bounded degree graphs. One can define convergence in terms of counting homomorphisms from fixed graphs into members of the sequence (left‐convergence), or counting homomorphisms into fixed graphs (right‐convergence). Under appropriate conditions, these two ways of defining convergence was proved to be equivalent in the dense case by Borgs, Chayes, Lovász, Sós and Vesztergombi. In this paper a similar equivalence is established in the bounded degree case, if the set of graphs in the definition of right‐convergence is appropriately restricted. In terms of statistical physics, the implication that left convergence implies right convergence means that for a left‐convergent sequence, partition functions of a large class of statistical physics models converge. The proof relies on techniques from statistical physics, like cluster expansion and Dobrushin Uniqueness. © 2012 Wiley Periodicals, Inc. Random Struct. 2012</description><identifier>ISSN: 1042-9832</identifier><identifier>EISSN: 1098-2418</identifier><identifier>DOI: 10.1002/rsa.20414</identifier><language>eng</language><publisher>Hoboken: Wiley Subscription Services, Inc., A Wiley Company</publisher><subject>cluster expansion ; Dobrushin Uniqueness ; graph limits ; left convergence ; right convergence</subject><ispartof>Random structures &amp; algorithms, 2013-01, Vol.42 (1), p.1-28</ispartof><rights>Copyright © 2012 Wiley Periodicals, Inc.</rights><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c3354-ae18d3af6109d2ace27a017860099c497c02c995b4b76f43b137637073332c183</citedby><cites>FETCH-LOGICAL-c3354-ae18d3af6109d2ace27a017860099c497c02c995b4b76f43b137637073332c183</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><link.rule.ids>314,780,784,27924,27925</link.rule.ids></links><search><creatorcontrib>Borgs, Christian</creatorcontrib><creatorcontrib>Chayes, Jennifer</creatorcontrib><creatorcontrib>Kahn, Jeff</creatorcontrib><creatorcontrib>Lovász, László</creatorcontrib><title>Left and right convergence of graphs with bounded degree</title><title>Random structures &amp; algorithms</title><addtitle>Random Struct. Alg</addtitle><description>The theory of convergent graph sequences has been worked out in two extreme cases, dense graphs and bounded degree graphs. One can define convergence in terms of counting homomorphisms from fixed graphs into members of the sequence (left‐convergence), or counting homomorphisms into fixed graphs (right‐convergence). Under appropriate conditions, these two ways of defining convergence was proved to be equivalent in the dense case by Borgs, Chayes, Lovász, Sós and Vesztergombi. In this paper a similar equivalence is established in the bounded degree case, if the set of graphs in the definition of right‐convergence is appropriately restricted. In terms of statistical physics, the implication that left convergence implies right convergence means that for a left‐convergent sequence, partition functions of a large class of statistical physics models converge. The proof relies on techniques from statistical physics, like cluster expansion and Dobrushin Uniqueness. © 2012 Wiley Periodicals, Inc. Random Struct. 2012</description><subject>cluster expansion</subject><subject>Dobrushin Uniqueness</subject><subject>graph limits</subject><subject>left convergence</subject><subject>right convergence</subject><issn>1042-9832</issn><issn>1098-2418</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2013</creationdate><recordtype>article</recordtype><recordid>eNp1kD1PwzAQhi0EEqUw8A8sMTGk9Vdie6wKFFAFEgUhsViOc0lTSlLslNJ_T0qAjelueJ67Vy9Cp5QMKCFs6IMdMCKo2EM9SrSKmKBqf7cLFmnF2SE6CmFBCJGc8R5SU8gbbKsM-7KYN9jV1Qf4AioHuM5x4e1qHvCmbOY4rddVBhnOoPAAx-ggt8sAJz-zj56uLh_H19H0fnIzHk0jx3ksIgtUZdzmSRsmY9YBk5ZQqRJCtHZCS0eY0zpORSqTXPCUcplw2abjnDmqeB-ddXdXvn5fQ2jMol77qn1pKJWJbjEVt9R5Rzlfh-AhNytfvlm_NZSYXTGmLcZ8F9Oyw47dlEvY_g-ah9no14g6owwNfP4Z1r-aRHIZm-e7iSG3kumXC2Fm_AtZJ3DA</recordid><startdate>201301</startdate><enddate>201301</enddate><creator>Borgs, Christian</creator><creator>Chayes, Jennifer</creator><creator>Kahn, Jeff</creator><creator>Lovász, László</creator><general>Wiley Subscription Services, Inc., A Wiley Company</general><general>Wiley Subscription Services, Inc</general><scope>BSCLL</scope><scope>AAYXX</scope><scope>CITATION</scope><scope>7SC</scope><scope>8FD</scope><scope>JQ2</scope><scope>L7M</scope><scope>L~C</scope><scope>L~D</scope></search><sort><creationdate>201301</creationdate><title>Left and right convergence of graphs with bounded degree</title><author>Borgs, Christian ; Chayes, Jennifer ; Kahn, Jeff ; Lovász, László</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c3354-ae18d3af6109d2ace27a017860099c497c02c995b4b76f43b137637073332c183</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2013</creationdate><topic>cluster expansion</topic><topic>Dobrushin Uniqueness</topic><topic>graph limits</topic><topic>left convergence</topic><topic>right convergence</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Borgs, Christian</creatorcontrib><creatorcontrib>Chayes, Jennifer</creatorcontrib><creatorcontrib>Kahn, Jeff</creatorcontrib><creatorcontrib>Lovász, László</creatorcontrib><collection>Istex</collection><collection>CrossRef</collection><collection>Computer and Information Systems Abstracts</collection><collection>Technology Research Database</collection><collection>ProQuest Computer Science Collection</collection><collection>Advanced Technologies Database with Aerospace</collection><collection>Computer and Information Systems Abstracts – Academic</collection><collection>Computer and Information Systems Abstracts Professional</collection><jtitle>Random structures &amp; algorithms</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Borgs, Christian</au><au>Chayes, Jennifer</au><au>Kahn, Jeff</au><au>Lovász, László</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Left and right convergence of graphs with bounded degree</atitle><jtitle>Random structures &amp; algorithms</jtitle><addtitle>Random Struct. Alg</addtitle><date>2013-01</date><risdate>2013</risdate><volume>42</volume><issue>1</issue><spage>1</spage><epage>28</epage><pages>1-28</pages><issn>1042-9832</issn><eissn>1098-2418</eissn><abstract>The theory of convergent graph sequences has been worked out in two extreme cases, dense graphs and bounded degree graphs. One can define convergence in terms of counting homomorphisms from fixed graphs into members of the sequence (left‐convergence), or counting homomorphisms into fixed graphs (right‐convergence). Under appropriate conditions, these two ways of defining convergence was proved to be equivalent in the dense case by Borgs, Chayes, Lovász, Sós and Vesztergombi. In this paper a similar equivalence is established in the bounded degree case, if the set of graphs in the definition of right‐convergence is appropriately restricted. In terms of statistical physics, the implication that left convergence implies right convergence means that for a left‐convergent sequence, partition functions of a large class of statistical physics models converge. The proof relies on techniques from statistical physics, like cluster expansion and Dobrushin Uniqueness. © 2012 Wiley Periodicals, Inc. Random Struct. 2012</abstract><cop>Hoboken</cop><pub>Wiley Subscription Services, Inc., A Wiley Company</pub><doi>10.1002/rsa.20414</doi><tpages>28</tpages></addata></record>
fulltext fulltext
identifier ISSN: 1042-9832
ispartof Random structures & algorithms, 2013-01, Vol.42 (1), p.1-28
issn 1042-9832
1098-2418
language eng
recordid cdi_proquest_journals_1176933285
source Wiley-Blackwell Read & Publish Collection
subjects cluster expansion
Dobrushin Uniqueness
graph limits
left convergence
right convergence
title Left and right convergence of graphs with bounded degree
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-01T07%3A12%3A57IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Left%20and%20right%20convergence%20of%20graphs%20with%20bounded%20degree&rft.jtitle=Random%20structures%20&%20algorithms&rft.au=Borgs,%20Christian&rft.date=2013-01&rft.volume=42&rft.issue=1&rft.spage=1&rft.epage=28&rft.pages=1-28&rft.issn=1042-9832&rft.eissn=1098-2418&rft_id=info:doi/10.1002/rsa.20414&rft_dat=%3Cproquest_cross%3E2820267241%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c3354-ae18d3af6109d2ace27a017860099c497c02c995b4b76f43b137637073332c183%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=1176933285&rft_id=info:pmid/&rfr_iscdi=true