Convergent Sequences of Dense Graphs I: Subgraph Frequencies, Metric Properties and Testing
By Christian Borgs, Jennifer Tour Chayes, L. Lov'asz, Vera T. Sós, Katalin Vesztergombi. 2007
699 citations recorded by the source corpus.
We consider sequences of graphs (Gn) and define various notions of convergence related to these sequences: “left convergence” defined in terms of the densities of homomorphisms from small graphs into Gn; “right convergence” defined in terms of the densities of homomorphisms from Gn into small graphs; and convergence in a suitably defined metric. In Part I of this series, we show that left convergence is equivalent to convergence in metric, both for simple graphs Gn, and for graphs Gn with nodeweights and edgeweights. One of the main steps here is the introduction of a cut-distance comparing graphs, not necessarily of the same size. We also show how these notions of convergence provide natural
Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Geometry and Topology
View Paper: https://www.semanticscholar.org/paper/be033f227bc5aeed0702d2beb944b1068b274cfa
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
- Sourav Chatterjee
- Svante Janson
- Persi Diaconis
- Roberto Imbuzeiro Oliveira
- L. Lov'asz
- Charles Bordenave
- Oliver Riordan
- Béla Bollobás
In Discrete Mathematics and Combinatorics
- Sourav Chatterjee
- Persi Diaconis
- L. Lov'asz
- Svante Janson
- Charles Bordenave
- Roberto Imbuzeiro Oliveira
- Pietro Caputo
- Béla Bollobás
In Geometry and Topology
- Sourav Chatterjee
- Persi Diaconis
- Svante Janson
- L. Lov'asz
- Oliver Riordan
- Béla Bollobás
- S. Varadhan
- Amir Dembo
Citations in the corpus
- An introduction to large deviations for random graphs (2016, background): “A beautiful unifying theory of graph limits has been developed by Laszlo Lovász and coauthors in recent years [8, 9, 10, 40, 41].”
- Mean-field and graph limits for collective dynamics models with time-varying weights (2020, methodology): “In 2014, Medvedev used techniques from the recent theory of graph limit [5, 4, 19, 20, 18] to derive rigorously the continuum limit of dynamical models on deterministic graphs [22].”
- Probability and Mathematical Genetics: More uses of exchangeability: representations of complex random structures (2009, background): “ts for a particular subclass of graphs called threshold graphs. Of course the line of work started in [47] has been developed further to produce new and interesting results in graph theory – see e.g. [21]. 5.2 Further uses in finitary combinatorics The remarkable recent survey by Austin [12] gives a ”
- Metrics for sparse graphs (2007, methodology): “Several of these metrics have been studied by Borgs, Chayes, Lovász, Sós and Vesztergombi [15, 16], who showed that they are equivalent, and that there is a natural completion of the space of graphs under any of these metrics.”
- The large deviation principle for the Erd\H{o}s-R\'enyi random graph (2010, methodology): “One of the key results of [6] is the following:”
- 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): “The four notions of convergence describe informally above, namely left convergence, right convergence, convergence in metric and convergence of quotients, were already introduced in [8, 9] in the context of sequences of dense graphs.”
- Percolation on dense graph sequences. (2007, neutral): “The Annals of Probability 2010, Vol. 38, No. 1, 150–183 DOI: 10.1214/09-AOP478 © Institute of Mathematical Statistics, 2010”
- Concentration of the adjacency matrix and of the Laplacian in random graphs with independent edges (2009, methodology): “A related random graph model generating dense graphs ( p = 1) was introduced in [49] and studied in [16].”
- Random graphs with a given degree sequence (2010, methodology): “Perhaps this can be established using the “cut-metric” of Frieze and Kannan, as expounded in [14].”