Categorical approach to graph limits

Abstract We define and study a natural category of graph limits. The objects are pairs $$(\pi ,\mu )$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>π</mml:mi> <mml:mo>,</mml:mo> <mml:mi>μ</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> , where $$\pi $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>π</mml:mi> </mml:math> (the distribution of vertices) is an abstract probability measure on some abstract measurable space $$(X,\mathcal {A})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>X</mml:mi> <mml:mo>,</mml:mo> <mml:mi>A</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> and $$\mu $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>μ</mml:mi> </mml:math> (the distribution of edges) is an abstract finite measure on the square $$(X,\mathcal {A})^2$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>X</mml:mi> <mml:mo>,</mml:mo> <mml:mi>A</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mn>2</mml:mn> </mml:msup> </mml:math> . 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.