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

  1. Sourav Chatterjee
  2. L. Lov'asz
  3. Persi Diaconis
  4. Svante Janson
  5. Charles Bordenave
  6. Oliver Riordan
  7. Béla Bollobás
  8. Jennifer Tour Chayes

In Discrete Mathematics and Combinatorics

  1. Sourav Chatterjee
  2. L. Lov'asz
  3. Persi Diaconis
  4. Charles Bordenave
  5. Svante Janson
  6. Tim Austin
  7. Pietro Caputo
  8. Peter Keevash

In Geometry and Topology

  1. Sourav Chatterjee
  2. L. Lov'asz
  3. Persi Diaconis
  4. Svante Janson
  5. Oliver Riordan
  6. Tim Austin
  7. Béla Bollobás
  8. S. Varadhan

Citations in the corpus