Convergent sequences of dense graphs II. Multiway cuts and statistical physics

Abstract

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.

  • [Bar] . Baranyai, "On the factorization of the complete uniform hypergraph," in Infinite and Finite Sets, Amsterdam: North-Holland, 1975, vol. 10, pp. 91-108.
    @incollection {Bar, MRKEY = {0416986},
      AUTHOR = {Baranyai, {Zs}.},
      TITLE = {On the factorization of the complete uniform hypergraph},
      BOOKTITLE = {Infinite and Finite Sets},
      PAGES = {91--108},
      SERIES={Colloq. Math. Soc. János Bolyai,},
      VOLUME={10},
      PUBLISHER = {North-Holland},
      ADDRESS = {Amsterdam},
      YEAR = {1975},
      MRCLASS = {05C99},
      MRNUMBER = {0416986},
      MRREVIEWER = {D. L. Greenwell},
      ZBLNUMBER = {0306.05137},
      }
  • [BBCR] Go to document B. Bollobás, C. Borgs, J. Chayes, and O. Riordan, "Percolation on dense graph sequences," Ann. Probab., vol. 38, iss. 1, pp. 150-183, 2010.
    @article {BBCR, MRKEY = {2599196},
      AUTHOR = {Bollob{á}s, B{é}la and Borgs, Christian and Chayes, Jennifer and Riordan, Oliver},
      TITLE = {Percolation on dense graph sequences},
      JOURNAL = {Ann. Probab.},
      FJOURNAL = {The Annals of Probability},
      VOLUME = {38},
      YEAR = {2010},
      NUMBER = {1},
      PAGES = {150--183},
      ISSN = {0091-1798},
      CODEN = {APBYAE},
      MRCLASS = {60K35 (05C12 05C80 60J80)},
      MRNUMBER = {2599196},
      MRREVIEWER = {Francis Comets},
      DOI = {10.1214/09-AOP478},
      ZBLNUMBER = {1190.60090},
      }
  • [BCLSV-1] Go to document C. Borgs, J. Chayes, L. Lovász, V. T. Sós, and K. Vesztergombi, "Counting graph homomorphisms," in Topics in Discrete Mathematics, New York: Springer-Verlag, 2006, vol. 26, pp. 315-371.
    @incollection {BCLSV-1, MRKEY = {2249277},
      AUTHOR = {Borgs, Christian and Chayes, Jennifer and Lov{á}sz, L{á}szl{ó} and S{ó}s, Vera T. and Vesztergombi, Katalin},
      TITLE = {Counting graph homomorphisms},
      BOOKTITLE = {Topics in Discrete Mathematics},
      SERIES = {Algorithms Combin.},
      VOLUME = {26},
      PAGES = {315--371},
      PUBLISHER = {Springer-Verlag},
      ADDRESS = {New York},
      YEAR = {2006},
      MRCLASS = {05C35 (82B99)},
      MRNUMBER = {2249277},
      MRREVIEWER = {David J. Galvin},
      DOI = {10.1007/3-540-33700-8_18},
      ZBLNUMBER = {1129.05050},
      }
  • [dense1] Go to document C. Borgs, J. T. Chayes, L. Lovász, V. T. Sós, and K. Vesztergombi, "Convergent sequences of dense graphs. I. Subgraph frequencies, metric properties and testing," Adv. Math., vol. 219, iss. 6, pp. 1801-1851, 2008.
    @article {dense1, MRKEY = {2455626},
      AUTHOR = {Borgs, C. and Chayes, J. T. and Lov{á}sz, L. and S{ó}s, V. T. and Vesztergombi, K.},
      TITLE = {Convergent sequences of dense graphs. {I}. {S}ubgraph frequencies, metric properties and testing},
      JOURNAL = {Adv. Math.},
      FJOURNAL = {Advances in Mathematics},
      VOLUME = {219},
      YEAR = {2008},
      NUMBER = {6},
      PAGES = {1801--1851},
      ISSN = {0001-8708},
      CODEN = {ADMTA4},
      MRCLASS = {05C80 (05C12 05C35 68R10)},
      MRNUMBER = {2455626},
      MRREVIEWER = {Michael Krivelevich},
      DOI = {10.1016/j.aim.2008.07.008},
      ZBLNUMBER = {1213.05161},
     }
  • [BCL] Go to document C. Borgs, J. Chayes, and L. Lovász, "Moments of two-variable functions and the uniqueness of graph limits," Geom. Funct. Anal., vol. 19, iss. 6, pp. 1597-1619, 2010.
    @article {BCL, MRKEY = {2594615},
      AUTHOR = {Borgs, Christian and Chayes, Jennifer and Lov{á}sz, L{á}szl{ó}},
      TITLE = {Moments of two-variable functions and the uniqueness of graph limits},
      JOURNAL = {Geom. Funct. Anal.},
      FJOURNAL = {Geometric and Functional Analysis},
      VOLUME = {19},
      YEAR = {2010},
      NUMBER = {6},
      PAGES = {1597--1619},
      ISSN = {1016-443X},
      CODEN = {GFANFB},
      MRCLASS = {05C60 (05C80 28D15 60C05)},
      MRNUMBER = {2594615},
      MRREVIEWER = {Christian Lavault},
      DOI = {10.1007/s00039-010-0044-0},
      ZBLNUMBER = {1223.05193},
      }
  • [CGW] Go to document F. R. K. Chung, R. L. Graham, and R. M. Wilson, "Quasi-random graphs," Combinatorica, vol. 9, iss. 4, pp. 345-362, 1989.
    @article {CGW, MRKEY = {1054011},
      AUTHOR = {Chung, F. R. K. and Graham, R. L. and Wilson, R. M.},
      TITLE = {Quasi-random graphs},
      JOURNAL = {Combinatorica},
      FJOURNAL = {Combinatorica. An International Journal on Combinatorics and the Theory of Computing},
      VOLUME = {9},
      YEAR = {1989},
      NUMBER = {4},
      PAGES = {345--362},
      ISSN = {0209-9683},
      CODEN = {COMBDI},
      MRCLASS = {05C80},
      MRNUMBER = {1054011},
      MRREVIEWER = {Zbigniew Palka},
      DOI = {10.1007/BF02125347},
      ZBLNUMBER = {0715.05057},
      }
  • [FK] Go to document A. Frieze and R. Kannan, "Quick approximation to matrices and applications," Combinatorica, vol. 19, iss. 2, pp. 175-220, 1999.
    @article {FK, MRKEY = {1723039},
      AUTHOR = {Frieze, Alan and Kannan, Ravi},
      TITLE = {Quick approximation to matrices and applications},
      JOURNAL = {Combinatorica},
      FJOURNAL = {Combinatorica. An International Journal on Combinatorics and the Theory of Computing},
      VOLUME = {19},
      YEAR = {1999},
      NUMBER = {2},
      PAGES = {175--220},
      ISSN = {0209-9683},
      MRCLASS = {68Q25 (05C85 15-04 68R10 68W20)},
      MRNUMBER = {1723039},
      MRREVIEWER = {Eugene V. Dulov},
      DOI = {10.1007/s004930050052},
      ZBLNUMBER = {0933.68061},
      }
  • [LS] Go to document L. Lovász and V. T. Sós, "Generalized quasirandom graphs," J. Combin. Theory Ser. B, vol. 98, iss. 1, pp. 146-163, 2008.
    @article {LS, MRKEY = {2368030},
      AUTHOR = {Lov{á}sz, L{á}szl{ó} and S{ó}s, Vera T.},
      TITLE = {Generalized quasirandom graphs},
      JOURNAL = {J. Combin. Theory Ser. B},
      FJOURNAL = {Journal of Combinatorial Theory. Series B},
      VOLUME = {98},
      YEAR = {2008},
      NUMBER = {1},
      PAGES = {146--163},
      ISSN = {0095-8956},
      CODEN = {JCBTB8},
      MRCLASS = {05C80},
      MRNUMBER = {2368030},
      MRREVIEWER = {Daniela K{ü}hn},
      DOI = {10.1016/j.jctb.2007.06.005},
      ZBLNUMBER = {1127.05094},
      }
  • [LSz] Go to document L. Lovász and B. Szegedy, "Limits of dense graph sequences," J. Combin. Theory Ser. B, vol. 96, iss. 6, pp. 933-957, 2006.
    @article {LSz, MRKEY = {2274085},
      AUTHOR = {Lov{á}sz, L{á}szl{ó} and Szegedy, Bal{á}zs},
      TITLE = {Limits of dense graph sequences},
      JOURNAL = {J. Combin. Theory Ser. B},
      FJOURNAL = {Journal of Combinatorial Theory. Series B},
      VOLUME = {96},
      YEAR = {2006},
      NUMBER = {6},
      PAGES = {933--957},
      ISSN = {0095-8956},
      CODEN = {JCBTB8},
      MRCLASS = {05C35 (05C50 05C80)},
      MRNUMBER = {2274085},
      MRREVIEWER = {Yoshiharu Kohayakawa},
      DOI = {10.1016/j.jctb.2006.05.002},
      ZBLNUMBER = {1113.05092},
      }
  • [LSz-Anal] Go to document L. Lovász and B. Szegedy, "Szemerédi’s lemma for the analyst," Geom. Funct. Anal., vol. 17, iss. 1, pp. 252-270, 2007.
    @article {LSz-Anal, MRKEY = {2306658},
      AUTHOR = {Lov{á}sz, L{á}szl{ó} and Szegedy, Bal{á}zs},
      TITLE = {Szemerédi's lemma for the analyst},
      JOURNAL = {Geom. Funct. Anal.},
      FJOURNAL = {Geometric and Functional Analysis},
      VOLUME = {17},
      YEAR = {2007},
      NUMBER = {1},
      PAGES = {252--270},
      ISSN = {1016-443X},
      CODEN = {GFANFB},
      MRCLASS = {05C35 (46B99 46E99)},
      MRNUMBER = {2306658},
      DOI = {10.1007/s00039-007-0599-6},
      ZBLNUMBER = {1123.46020},
      }
  • [LSz-test] Go to document L. Lovász and B. Szegedy, "Testing properties of graphs and functions," Israel J. Math., vol. 178, pp. 113-156, 2010.
    @article {LSz-test, MRKEY = {2733066},
      AUTHOR = {Lov{á}sz, L{á}szl{ó} and Szegedy, Bal{á}zs},
      TITLE = {Testing properties of graphs and functions},
      JOURNAL = {Israel J. Math.},
      FJOURNAL = {Israel Journal of Mathematics},
      VOLUME = {178},
      YEAR = {2010},
      PAGES = {113--156},
      ISSN = {0021-2172},
      CODEN = {ISJMAP},
      MRCLASS = {05C85 (05C75 05E05)},
      MRNUMBER = {2733066},
      DOI = {10.1007/s11856-010-0060-7},
      ZBLNUMBER = {05823069},
      }
  • [Tho] A. Thomason, "Pseudorandom graphs," in Random Graphs ’85, Amsterdam: North-Holland, 1987, vol. 144, pp. 307-331.
    @incollection {Tho, MRKEY = {0930498},
      AUTHOR = {Thomason, Andrew},
      TITLE = {Pseudorandom graphs},
      BOOKTITLE = {Random Graphs '85},
      VENUE={{P}oznań, 1985},
      SERIES = {North-Holland Math. Stud.},
      VOLUME = {144},
      PAGES = {307--331},
      PUBLISHER = {North-Holland},
      ADDRESS = {Amsterdam},
      YEAR = {1987},
      MRCLASS = {05C80},
      MRNUMBER = {0930498},
      MRREVIEWER = {Edward R. Scheinerman},
      ZBLNUMBER = {0632.05045},
     }
  • [S-Lem] E. Szemerédi, "Regular partitions of graphs," in Problèmes Combinatoires et Théorie des Graphes, Paris: CNRS, 1978, vol. 260, pp. 399-401.
    @incollection {S-Lem, MRKEY = {0540024},
      AUTHOR = {Szemer{é}di, Endre},
      TITLE = {Regular partitions of graphs},
      BOOKTITLE = {Problèmes Combinatoires et Théorie des Graphes},
      VENUE={{C}olloq. {I}nternat. {CNRS},
      {U}niv. {O}rsay, {O}rsay, 1976},
      SERIES = {Colloq. Internat. CNRS},
      VOLUME = {260},
      PAGES = {399--401},
      PUBLISHER = {CNRS},
      ADDRESS = {Paris},
      YEAR = {1978},
      MRCLASS = {05C35 (10L10)},
      MRNUMBER = {0540024},
      MRREVIEWER = {D. A. Klarner},
      ZBLNUMBER = {0413.05055},
      }

Authors

Christian Borgs

Microsoft Research
1 Memorial Drive
Cambridge, MA 02142

Jennifer T. Chayes

Microsoft Research
1 Memorial Drive
Cambridge, MA 02142

László Lovász

Department of Computer Science
Eötvös Loránd University
H-1518 Budapest
Hungary

Vera T. Sós

Alfréd Rényi
Institute of Mathematics
Hungarian Academy of Sciences
H-1364 Budapest
Hungary

Katalin Vesztergombi

Department of Computer Science
Eötvös Loránd University
H-1518 Budapest
Hungary