Limits of local-global convergent graph sequences

Abstract

The colored neighborhood metric for sparse graphs was introduced by Bollobás and Riordan. The corresponding convergence notion refines a convergence notion introduced by Benjamini and Schramm. We prove that even in this refined sense, the limit of a convergent graph sequence (with uniformly bounded degree) can be represented by a graphing. We study various topics related to this convergence notion such as: Bernoulli graphings, factor of i.i.d. processes and hyperfiniteness.

25 pages

References in corpus (2)

• The combinatorial cost
• A measure-theoretic approach to the theory of dense hypergraphs

Cited by in corpus (10)

• Local algorithms for independent sets are half-optimal
• Finding One Community in a Sparse Graph
• A determinacy approach to Borel combinatorics
• Invariant random matchings in Cayley graphs
• Factor of iid percolation on trees
• Performance of the Survey Propagation-guided decimation algorithm for the random NAE-K-SAT problem
• Global and Local Information in Clustering Labeled Block Models
• Finite graphs and amenability
• Local Algorithms for Block Models with Side Information
• Local approximation of the Maximum Cut in regular graphs