Categorical approach to graph limits

Martin Doležal, 6 Nov 2023

The use of category theory in graph theory is quite common. We show that category theory may be useful even in the world of graph limits. To do so, we introduce a new category whose objects are certain generalizations of graphs where both distributions of vertices and edges are represented by abstract measures. This is a similar (but more general) approach as that of s-graphons introduced by D. Kunszenti-Kovács, L. Lovász, and B. Szegedy in 2019. A morphism in our category can be viewed as a ‘fuzzy’ map between the underlying measurable spaces. The values of this map are not defined deterministically, we only know the probability that a given point is mapped to a given set. Formally, this idea is realized with the use of Markov kernels which, in a certain sense, preserve the distributions of vertices and edges. Further, we introduce a natural notion of convergence of sequences of graphs (or, more generally, of objects of our category) which is heavily inspired by convergence of s-graphons. Then we apply the categorical structure to show that each convergent sequence has a limit object.