Warwick's combinatorics seminar in 2020-21 will be held online 2-3pm UK time on Fridays (which is UTC+01:00 until 25 October 2020 and then coincides with UTC).
Meeting ID: 833 1416 5275
László Lovász (Budapest)
Marthe Bonamy (Bordeaux)
Gábor Tardos (Budapest)
|Convergence and limits of finite trees|
|30 Oct||Maria Chudnovsky (Princeton)|
|13 Nov||Tibor Szabó (Berlin)|
|20 Nov||Benny Sudakov (Zurich)|
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.
Given a solution to a problem, we can try and apply a series of elementary operations to it, making sure to remain in the solution space at every step. What kind of solutions can we reach this way? How fast? This is motivated by a variety of applications, from statistical physics to real-life scenarios, including enumeration and sampling. In this talk, we will discuss various positive and negative results, in the special case of graph colouring.
Convergence and limits of finite trees (Gábor Tardos), 14:00, ZOOM, slides
Seeing the success of limit theory of dense finite graphs with graphons as their limit objects we developed a similar (?) theory for finite trees. In order for the sampling limit to make sense we need to make the trees "dense" - we do this by considering them as metric spaces with the normalized graph distance. Using ultaproducts is a simple and elegant way to find unique limit objects (we call them dendrons) and also to highlight similarities and major differences from the theory of dense graph limits. For the underlying quantitative approximation results, one needs more "down to earth" techniques to be developed.
This is joint work with Gábor Elek.