Graph limits, measures, and flows

Abstract: The theory of graph limits is only understood to a somewhat satisfactory degree in the cases of dense graphs and of bounded degree graphs. There is, however, a lot of interest in the intermediate cases. It appears that the most important constituents of graph limits in the general case will be Markov spaces (Markov chains on measurable spaces with a stationary distribution).

This motivates our goal to extend some important theorems from finite graphs to Markov spaces or, more generally, to measurable spaces. In this talk we show that much of flow theory, one of the most important areas in graph theory, can be extended to measurable spaces. In particular, the Hoffman Circulation Theorem, the Max-Flow-Min-Cut Theorem, Multicommodity Flow Theorem, and several other results have simple and elegant extensions to measures.

combinatorics

Audience: researchers in the topic

Warwick Combinatorics Seminar

Series comments: This is the online combinatorics seminar at Warwick.