Convergent sequences of sparse graphs: a large deviations approach

DOI10.1002/RSA.20694MaRDI QIDQ5360869zbMATH OpenOpenAlexFDO

Authors David Gamarnik, Christian Borgs, Jennifer T. Chayes

Publication date 26 September 2017

Full work available at URL https://arxiv.org/abs/1302.4615

zbMATH Keywords

combinatorial optimizationgraph convergencesparse graphsstatistical physics

Mathematics Subject Classification ID

Density (toughness, etc.) (05C42) Combinatorial optimization (90C27)

Abstract: In this paper we introduce a new notion of convergence of sparse graphs which we call Large Deviations or LD-convergence and which is based on the theory of large deviations. The notion is introduced by "decorating" the nodes of the graph with random uniform i.i.d. weights and constructing random measures on $[0,1]$ and $[0,1{]}^2$ based on the decoration of nodes and edges. A graph sequence is defined to be converging if the corresponding sequence of random measures satisfies the Large Deviations Principle with respect to the topology of weak convergence on bounded measures on $[0,1{]}^d,d=1,2$. We then establish that LD-convergence implies several previous notions of convergence, namely so-called right-convergence, left-convergence, and partition-convergence. The corresponding large deviation rate function can be interpreted as the limit object of the sparse graph sequence. In particular, we can express the limiting free energies in terms of this limit object.

Recommendations

• An \(L^{p}\) theory of sparse graph convergence. II: LD convergence, quotients and right convergence
• Right-convergence of sparse random graphs
• Convergent sequences of dense graphs. II. Multiway cuts and statistical physics
• On limits of sparse random graphs
• Measures on the square as sparse graph limits

Cited in

(10)

• An \(L^{p}\) theory of sparse graph convergence. II: LD convergence, quotients and right convergence
• Convergent sequences of dense graphs. II. Multiway cuts and statistical physics
• Sparse graphs using exchangeable random measures
• Right-convergence of sparse random graphs
• Left and right convergence of graphs with bounded degree
• First order limits of sparse graphs: plane trees and path-width
• The interpolation method for random graphs with prescribed degrees
• Ordered graph limits and their applications
• Strong modeling limits of graphs with bounded tree-width
• A short proof of the equivalence of left and right convergence for sparse graphs

This page was built for publication: Convergent sequences of sparse graphs: a large deviations approach

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5360869)