Limits of dense graph sequences
By L. Lov'asz, Balázs Szegedy. J. Comb. Theory B, 2004
974 citations recorded by the source corpus.
We show that if a sequence of dense graphs G"n has the property that for every fixed graph F, the density of copies of F in G"n tends to a limit, then there is a natural ''limit object,'' namely a symmetric measurable function W:[0,1]^2->[0,1]. This limit object determines all the limits of subgraph densities. Conversely, every such function arises as a limit object. We also characterize graph parameters that are obtained as limits of subgraph densities by the ''reflection positivity'' property. Along the way we introduce a rather general model of random graphs, which seems to be interesting on its own right.
Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Geometry and Topology
View Paper: https://www.semanticscholar.org/paper/4b5960dc56bdf567fa5ba2fd906736604013b509
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
- L. Lov'asz
- Persi Diaconis
- Svante Janson
- Charles Bordenave
- Oliver Riordan
- Béla Bollobás
- Jennifer Tour Chayes
In Discrete Mathematics and Combinatorics
- Sourav Chatterjee
- L. Lov'asz
- Persi Diaconis
- Charles Bordenave
- Svante Janson
- Tim Austin
- Pietro Caputo
- Peter Keevash
In Geometry and Topology
- Sourav Chatterjee
- L. Lov'asz
- Persi Diaconis
- Svante Janson
- Oliver Riordan
- Tim Austin
- Béla Bollobás
- S. Varadhan
Citations in the corpus
- Graph limits and exchangeable random graphs (2007, background): “, vk of vertices in G contains some repeated vertex is ≤ k2/(2v(G)), it follows that [21] ∣∣t(F,G)− tinj(F,G)∣∣ ≤ v(F )2 2v(G) .”
- Econometrics of Network Formation (2016, background): “Then there is a unique function h : [0, 1]→ R such that W (x, y) := exp(h(x) + h(y))1 + exp(h(x) + h(y)) , f(x) = ˆ 1 0 W (x, y)dy, and {gn} converges, in the sense described by Lovász and Szegedy (2006), almost surely to the limit represented by W (x, y).”
- Recurrence of planar graph limits (2012, background): “Convergence of sequences of dense graphs requires quite a different treatment (see [22], [11]) though some interesting connections between the two are emerging (see [10]).”
- A measure-theoretic approach to the theory of dense hypergraphs (2008, background): “5 in [10], that was used for the case k = 2.”
- Regularity Partitions and The Topology of Graphons (2010, background): “One can define convergence of a growing graph sequence [4, 3, 5], and construct a limit object to such a sequence [11] in the form of a symmetric measurable function W : J × J → [0, 1], where J is any probability space (one may assume here that J = [0, 1] with the Lebesgue measure, but this is not a”
- 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 [14], in the framework of the cut topology introduced by Lovász and Szegedy [24], see also Borgs, Chayes, Lovász, Sós and Vesztergombi [10,11].”
- An introduction to large deviations for random graphs (2016, background): “Or do they occur because the graph has an excess number of edges spread uniformly?”
- ON possible Turán densities (2012, neutral): “[5, 13, 28, 29].”
- Metrics for sparse graphs (2007, methodology): “As shown by Lovász and Szegedy [34] (see their Lemmas 5.”
- On exchangeable random variables and the statistics of large graphs and hypergraphs (2008, background): “In fact, Elek and Szegedy’s use of ultralimits has a predecessor in Hoover’s approach to the basic representation theorems for exchangeable arrays of random variables, as outlined in [42].”
- Mean-field and graph limits for collective dynamics models with time-varying weights (2020, neutral): “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): “ indicated above, the partially exchangeable representation theorem (Theorem 1) characterizes the possible limit structures S∞. A recent line of work in graph theory, initiated by Lov´asz and Szegedy [47], started by defining convergence in the equivalent way via (10) and obtained the same characteri”
- Random graph asymptotics for treatment effect estimation under network interference (2020, background): “Lovász and Szegedy (2006) show that a graphon limit arises naturally by considering any sequence of dense graphs En with the property that, for any fixed graph F , the density of copies of F in En tends to a limit.”
- Convergent Sequences of Dense Graphs I: Subgraph Frequencies, Metric Properties and Testing (2007, background): “The first statement of this theorem is closely related to the “Counting Lemma” in the theory of Szemerédi partitions, and gives an extension of a similar result of [26] for functions in W[0,1] to general graphons.”
- Estimating and understanding exponential random graph models (2011, methodology): “The main result of [40] (following the earlier equivalent work of Aldous [1] and Hoover [33]) is that indeed there is a natural “limit object” in the form of a function h ∈ W , where W is the space of all measurable functions from [0,1]2 into [0,1] that satisfy h(x, y) = h(y, x) for all x, y.”
- Surveys in Combinatorics 2011: Hypergraph Turán problems (2011, methodology): “Graph limits were first studied by Borgs, Chayes, Lovász, Sós and Vesztergombi (2003 unpublished and [24]) and by Lovász and Szegedy [126].”
- Large Networks and Graph Limits (2012, background): “(See Kozlov [2008] and Matoušek [2003] for detailed treatments of this topic.”