TCC Course "Graph Limits"
Here are the supplementary materials for the course (including homework assignments and a summary of notation).
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
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.
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:
- V.I.Bogachev "Measure Theory", Springer, 2007
- J.A.Bondy and U.S.R.Murty "Graph Theory", Springer 2008
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):
- J.Hirst, The Inducibility of Graphs
on Four Vertices, to appear in J Graph Theory
- C.Hoppen, Y.Kohayakawa, C.G.Moreira, B.Rath, and R.M.Sampaio,
Limits of permutation sequences, J. Combin. Theory (B) 103 (2013), 93–113.
- D.Kral' and O.Pikhurko, Quasirandom Permutations Are Characterized by 4-Point Densities, Geometric Funct Analysis, 23 (2013) 570-579.
- L.Lovasz and B.Szegedy, Limits of dense graph sequences, J. Combin.
Theory (B) 96 (2006), 933-957.
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.
Please email email@example.com (and cc: to me) if you'd like
to be added to the emailing list of the course (which will
be used for various
If you have any course-related
questions, please post them at the discussion group of the course:
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)