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

MSR-TR-2008-199 |

For a symmetric bounded measurable function W on [0,1]2 and a simple graph F, the homomorphism density 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.