TCC Course "Graph Limits"

Online Materials

Here are the supplementary materials for the course (including homework assignments and a summary of notation).

StarBoard images:

Short Description

The course will concentrate on the emerging theory of limits of graphs and other discrete structures. This is a relatively new but general and promising concept that relates finite combinatorics to analysis, probability, semi-definite optimisation, and many other areas. A possible way to define limits of structures is to consider some distance that measures how similar two combinatorial objects are and take the completion of the space of all finite object. The potential power of this approach lies in the remarkable fact that for many natural distances the obtained (larger) space can be constructed in genuinely different ways.

For example, the cut distance of Frieze and Kannan on dense graphs leads to limits objects that can be alternatively represented by measurable functions, exchangeable distributions on countable graphs, or flag algebra homomorphisms. On the other hand, the Benjamini-Schramm convergence on bounded-degree graphs leads to so-called graphings, which can be viewed as some version of dynamical systems.

Graph limits have already found a number of applications: in (finite) extremal combinatorics, property testing, and statistical physics. Also, Regularity Lemmas play a very important role in this area.

Prerequisites

A good familiarity with the basics of graph theory and measure theory will be assumed. The recommended general references (if you need to revise some topic) are:

Time

The lectures will take place 4-6pm on Tuesdays, 15th October - 3rd December 2013.

Textbooks and Supplementary Reading

The course will be based on the book L.Lovasz "Large Networks and Graph Limits", American Mathematical Society, 2012 and the following research articles (this list will be updated as the course progresses):

Assessment

Those participants who need a grade will have to write an essay presenting one of the papers listed here.

The aim of each essay is to understand some further results and explain them in a way accessible to other course participants. The deadline for submitting essays will be 17 December 2013.

Emailing list

Please email graduate.studies@maths.ox.ac.uk (and cc: to me) if you'd like to be added to the emailing list of the course (which will be used for various announcements, etc).

Getting help

If you have any course-related questions, please post them at the discussion group of the course:

https://groups.google.com/d/forum/graph-limits

Also, other messages related to the course are welcome on the forum. In particular, if you see a question by somebody else and you know the answer or just want to add a comment, you are very welcome to post a follow-up message. I will be checking the group regularly and posting replies to any queries that still need answers.


Oleg Pikhurko (O dot Pikhurko at warwick dot ac dot uk)