Set Theory & Analysis

Categorical approach to graph limits

Martin Doležal

IM CAS

Tuesday, 21. March 2023 - 10:00 to 11:30

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 Kunszenti-Kovács, Lovász, and Szegedy in their paper on s-convergence. A morphism in our category can be viewed as a ‘fuzzy’ map between the underlying 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 s-convergence. Then we apply the categorical structure to show that each convergent sequence has a limit object.

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 s-convergence. Then we apply the categorical structure to show that each convergent sequence has a limit object.

This is a joint work with Wiesław Kubiś.

IM in konírna