Convergent Sequences of Dense Graphs II. Multiway Cuts and Statistical Physics

By Christian Borgs, Jennifer Tour Chayes, L. Lov'asz, Vera T. Sós, Katalin Vesztergombi. 2012

355 citations recorded by the source corpus.

Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/3ecc15e93e1c07c10590da7060bab2a49854ebee

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Discrete Mathematics and Combinatorics

In Geometry and Topology

Citations in the corpus

Large deviations of empirical neighborhood distribution in sparse random graphs (2013, methodology): “G(n, p) with fixed p ∈ (0, 1), a thorough treatment has been given recently by Chatterjee and Varadhan [16], in the framework of the cut topology introduced by Lovász and coauthors, see Borgs, Chayes, Lovász, Sós and Vesztergombi [12]-[13].”
An $L^{p}$ theory of sparse graph convergence II: LD convergence, quotients and right convergence (2014, methodology): “(In [9], εn was chosen to be αmax(Gn)/αGn , even though all theorems involving the microcanonical free energies required the additional assumption that Gn has vertex weights one, corresponding to εn = 1/|V (Gn)|.”
Graphons, cut norm and distance, couplings and rearrangements (2010, neutral): “C O ] 3 J un 2”
Matrix estimation by Universal Singular Value Thresholding (2012, background): “The term ‘graphon’ was coined by Lov´asz and coauthors in the growing literature on limits of dense graphs [19, 20, 21, 69, 68].”
Nonlinear large deviations (2014, methodology): “The main tool in these papers is the regularity lemma of Sze-mer´edi [30] and the graph limit theory of Lov´asz and coauthors [4, 5, 26] that builds on the regularity lemma.”
Concentration of the adjacency matrix and of the Laplacian in random graphs with independent edges (2009, background): “For bounded kernels ( p = Θ (1)), this is easy enough (see [17, Theorem 6.6]), but there are diﬃculties in extending this to the sparse case.”
A problem of Erdős and Sós on 3-graphs (2013, methodology): “gebras. They were introduced by Razborov [21] as a general tool to approach problems from extremal combinatorics. The work of Razborov was inspired by the theory of dense graph limits of Borgs et al. [6, 7] and Lov´asz and Szegedy [19]. However, unlike for the more powerful Lov´asz-Szegedy theory, i”
Estimating and understanding exponential random graph models (2011, methodology): “Fortunately, it is an easy fact that the homomorphism density t (H, ·) is continuous for any finite simple graph H [10, 11].”
Percolation on dense graph sequences. (2007, background): “In [15] it is also shown that convergence implies convergence of the normalized spectra of the adjacency matrices to the spectrum of the limiting graphon considered as an operator on L2([0,1]).”
Upper tails and independence polynomials in random graphs (2015, background): “where symmetric means W(x;y) = W(y;x)); in the continuous version of (1.5), W will replace the edge-weighted graph Gn, as the latter can be viewed as a discrete approximation of a graphon (see, e.g., [2,3,19,21] for more on graph limits). As we will later see in x7 (see Lemma 7.1), the solution to t”
Random graphs with a given degree sequence (2010, methodology): “We quote the definition verbatim from [34] (see also [14, 15, 19]).”
Asymptotic behavior and distributional limits of preferential attachment graphs (2014, background): “In particular, there has been a series of papers on a notion of graph limits defined via graph homomorphisms [11–13, 20]; these have been shown to be equivalent to limits defined in many other senses [12, 13].”