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

Abstract

For a symmetric bounded measurable function W on [0, 1]² 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 (G _n ) of dense graphs is said to be convergent if the probability, t(F, G _n ), that a random map from V(F) into V(G _n ) 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]². Our results imply in particular that the limit of a convergent graph sequence is unique up to measure preserving transformation.