Date:

Thu, 17/05/201812:45-14:00

Title: Large sparse networks, graph limits and group theory

Abstract:

Fix a number d and use the word "graph" to mean "a graph where each vertex has at most d neighbors". Given a sequence of finite graphs, is there a useful notion of a "limit graph". Yes! For this to make sense, we need to add measure theory to the discussion. Specifically, we assume that the vertices of each graph are the elements of a probability space, and that the graph structure "respects" the probability measure (we'll make this precise). On finite graphs, we just use the uniform probability measure on the finite set of vertices. However, the limit graph of a sequence of finite graphs is (usually) a graph whose vertex set is an uncountable probability space!

A theory of such "measure preserving graphs" has emerged in the last two decades. While most known results concern graphs with many edges, the talk will concentrate on the more difficult (but more useful) theory of bounded-degree graphs (as described in the first paragraph).

The talk will not give a survey of this rich theory. Rather, we will focus on some gems it has to offer, and applications to group theory and algorithms.

The talk will be given in English.

Abstract:

Fix a number d and use the word "graph" to mean "a graph where each vertex has at most d neighbors". Given a sequence of finite graphs, is there a useful notion of a "limit graph". Yes! For this to make sense, we need to add measure theory to the discussion. Specifically, we assume that the vertices of each graph are the elements of a probability space, and that the graph structure "respects" the probability measure (we'll make this precise). On finite graphs, we just use the uniform probability measure on the finite set of vertices. However, the limit graph of a sequence of finite graphs is (usually) a graph whose vertex set is an uncountable probability space!

A theory of such "measure preserving graphs" has emerged in the last two decades. While most known results concern graphs with many edges, the talk will concentrate on the more difficult (but more useful) theory of bounded-degree graphs (as described in the first paragraph).

The talk will not give a survey of this rich theory. Rather, we will focus on some gems it has to offer, and applications to group theory and algorithms.

The talk will be given in English.