Integration and measures on the space of countable labelled graphs

Abstract

In this paper we develop a rigorous foundation for the study of integration and measures on the space $\mathcal{G}(V)$ of all graphs defined on a countable labelled vertex set $V$. We first study several interrelated $\sigma$-algebras and a large family of probability measures on graph space. We then focus on a "dyadic" Hamming distance function ${\Vert \cdot \Vert }_{\psi ,2}$, which was very useful in the study of differentiation on $\mathcal{G}(V)$. The function ${\Vert \cdot \Vert }_{\psi ,2}$ is shown to be a Haar measure-preserving bijection from the subset of infinite graphs to the circle (with the Haar/Lebesgue measure), thereby naturally identifying the two spaces. As a consequence, we establish a "change of variables" formula that enables the transfer of the Riemann-Lebesgue theory on $\mathbb{R}$ to graph space $\mathcal{G}(V)$. This also complements previous work in which a theory of Newton-Leibnitz differentiation was transferred from the real line to $\mathcal{G}(V)$ for countable $V$. Finally, we identify the Pontryagin dual of $\mathcal{G}(V)$, and characterize the positive definite functions on $\mathcal{G}(V)$.

15 pages, LaTeX