Coronavirus (Covid-19): Latest updates and information
Skip to main content Skip to navigation

Combinatorics Seminar 2020-21

Seminar organisers: Jan Grebík and Oleg Pikhurko

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).

Zoom link:
https://us02web.zoom.us/j/83314165275?pwd=TTZhNnpUZHJPdjFiekNtZTZQY1J2Zz09

Meeting ID: 833 1416 5275
Passcode: 757379

Term 1

Date Name Title
9 Oct

László Lovász (Budapest)

Graph limits, measures, and flows

16 Oct

Marthe Bonamy (Bordeaux)

Graph recolouring
23 Oct

Gábor Tardos (Budapest)

Convergence and limits of finite trees
30 Oct Maria Chudnovsky (Princeton)  
6 Nov    
13 Nov Tibor Szabó (Berlin)  
20 Nov Benny Sudakov (Zurich)  
4 Dec    
11 Dec    

Graph limits, measures, and flows (László Lovász), 14:00, ZOOM

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.

Graph recolouring (Marthe Bonamy), 14:00, ZOOM

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.