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

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

In Discrete Mathematics and Combinatorics

  1. Sourav Chatterjee
  2. Persi Diaconis
  3. L. Lov'asz
  4. Svante Janson
  5. Charles Bordenave
  6. Roberto Imbuzeiro Oliveira
  7. Pietro Caputo
  8. Béla Bollobás

In Geometry and Topology

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

Citations in the corpus