A short proof of the equivalence of left and right convergence for sparse graphs

DOI10.1016/J.EJC.2015.10.009zbMATH Open1328.05104arXiv1504.02892OpenAlexW2138690996MaRDI QIDQ901148FDOQ901148

Authors: László Miklós Lovász 

Publication date: 23 December 2015

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Abstract: There are several notions of convergence for sequences of bounded degree graphs. One such notion is left convergence, which is based on counting neighborhood distributions. Another notion is right convergence, based on counting homomorphisms to a target (weighted) graph. Borgs, Chayes, Kahn and Lov'asz showed that a sequence of bounded degree graphs is left convergent if and only if it is right convergent for certain target graphs $H$ with all weights (including loops) close to $1$. We give a short alternative proof of this statement. In particular, for each bounded degree graph $G$ we associate functions $f_{G,k}$ for every positive integer $k$, and we show that left convergence of a sequence of graphs is equivalent to the convergence of the partial derivatives of each of these functions at the origin, while right convergence is equivalent to pointwise convergence. Using the bound on the maximum degree of the graphs, we can uniformly bound the partial derivatives at the origin, and show that the Taylor series converges uniformly on a domain independent of the graph, which implies the equivalence.

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

Recommendations

• Left and right convergence of graphs with bounded degree
• Right-convergence of sparse random graphs
• Convergent sequences of dense graphs. II. Multiway cuts and statistical physics
• An \(L^{p}\) theory of sparse graph convergence. II: LD convergence, quotients and right convergence
• Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing

zbMATH Keywords

left convergencesequences of bounded degree graphsweighted target graph

Mathematics Subject Classification ID

Vertex degrees (05C07) Density (toughness, etc.) (05C42)

Cites Work

• Recurrence of distributional limits of finite planar graphs
• Endomorphisms of symbolic algebraic varieties
• Processes on unimodular random networks
• Convergent sequences of dense graphs. II. Multiway cuts and statistical physics
• Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
• Computing the partition function for graph homomorphisms
• Left and right convergence of graphs with bounded degree
• Limits of locally-globally convergent graph sequences
• Sparse graphs: metrics and random models
• Convergent sequences of sparse graphs: a large deviations approach

Cited In (4)

• Duality and free energy analyticity bounds for few-body Ising models with extensive homology rank
• Zero-free regions of partition functions with applications to algorithms and graph limits
• Left and right convergence of graphs with bounded degree
• Right-convergence of sparse random graphs

This page was built for publication: A short proof of the equivalence of left and right convergence for sparse graphs

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