<p>We define and study a natural category of graph limits. The objects are pairs <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$(\pi ,\mu )$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <mi>π</mi> <mo>,</mo> <mi>μ</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>, where <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$\pi $</EquationSource> <EquationSource Format="MATHML"><math> <mi>π</mi> </math></EquationSource> </InlineEquation> (the distribution of vertices) is an abstract probability measure on some abstract measurable space <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$(X,\mathcal {A})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <mi>X</mi> <mo>,</mo> <mi mathvariant="script">A</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$\mu $</EquationSource> <EquationSource Format="MATHML"><math> <mi>μ</mi> </math></EquationSource> </InlineEquation> (the distribution of edges) is an abstract finite measure on the square <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$(X,\mathcal {A})^2$</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mrow> <mo stretchy="false">(</mo> <mi>X</mi> <mo>,</mo> <mi mathvariant="script">A</mi> <mo stretchy="false">)</mo> </mrow> <mn>2</mn> </msup> </math></EquationSource> </InlineEquation>. 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.</p>

Categorical approach to graph limits

期刊论文
出版模式：

开放获取
发表日期：

2026年3月16日

查看全文

Martin Doležal,
Wiesław Kubiś

摘要

We define and study a natural category of graph limits. The objects are pairs $(\pi ,\mu )$ $(π, μ)$ , where $\pi $ $π$ (the distribution of vertices) is an abstract probability measure on some abstract measurable space $(X,\mathcal {A})$ $(X, A)$ and $\mu $ $μ$ (the distribution of edges) is an abstract finite measure on the square $(X,\mathcal {A})^2$ ${(X, 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.