Categorical approach to graph limits

Abstract

We define and study a natural category of graph limits. The objects are pairs $(\ddot{I}€,\hat{I}¼)$, where $\ddot{I}€$ (the distribution of vertices) is an abstract probability measure on some abstract measurable space $(X,\mathcal{A})$ and $\hat{I}¼$ (the distribution of edges) is an abstract finite measure on the square $(X,\mathcal{A}{)}^2$. Morphisms are random maps between the underlying measurable spaces which preserve the distribution of vertices as well as the distribution of edges. We also define a convergence notion (inspired by s-convergence) for sequences of graph limits. We apply tools from category theory to prove the compactness of the space of all graph limits.

43 pages