Moments of Two-Variable Functions and the Uniqueness of Graph Limits

By Christian Borgs, Jennifer Tour Chayes, L. Lov'asz. 2008

160 citations recorded by the source corpus.

AbstractFor a symmetric bounded measurable function W on [0, 1]2 and a simple graph F, the homomorphism density $$t(F,W) = \int _{[0,1]^{V (F)}} \prod_ {i j\in E(F)} W(x_i, x_j)dx .$$ can be thought of as a “moment” of W. We prove that every such function is determined by its moments up to a measure preserving transformation of the variables.The main motivation for this result comes from the theory of convergent graph sequences. A sequence (Gn) of dense graphs is said to be convergent if the probability, t(F, Gn), that a random map from V(F) into V(Gn) is a homomorphism converges for every simple graph F. The limiting density can be expressed as t(F, W) for a symmetric bounded measurable function W on [0, 1]2. Our results imply in particular that the limit of a convergent graph sequence is unique up to measure preserving transformation.

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

View Paper: https://www.semanticscholar.org/paper/6480801c03c06e1cbf01e1230b1f44acde729ba0

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

An $L^{p}$ theory of sparse graph convergence II: LD convergence, quotients and right convergence (2014, background): “2 in [6] is quite involved, we give here an alternative proof that δ1(Ũ , W̃ ) = 0 implies δ1(U,W) = 0 without using that result.”
Action convergence of operators and graphs (2018, background): “Remark 1.5 In dense graph limit theory, there is a rather natural answer to the question when two graphons are isomorphic, i.e., their δ ◻ distance is 0 [10].”
Graphons, cut norm and distance, couplings and rearrangements (2010, unknown): “C O ] 3 J un 2”
Metrics for sparse graphs (2007, background): “Fortunately, this situation has now been resolved: Borgs, Chayes and Lovász [12] have given a very clever direct proof of Theorem 2.8.”
Limits of locally–globally convergent graph sequences (2012, background): “…that µ extends from these boxes to a probability measure on all Borel sets in ∆ (in ergodic theory, this construction is called the relatively independent joining of the measures ν i over the common factor ν ; see e.g. [9], Lemma 6.2 for a detailed description of this construction for two factors).”