Skip to main content Skip to navigation

MA9M2 Topics in Combinatorics

Lecturer: Prof. Oleg Pikhurko

Term: Term 2

Commitment: 30 Lectures (10-12 on Mondays and 10-11 on Wednesdays in Zeeman D1.07 unless moved online)

Assessment: Oral Examination 100%

Outline syllabus:

In 2021-22, this module will concentrate on the emerging theory of the limits of discrete structures which, besides of being of independent interest, builds a two-way bridge connecting combinatorics to other fields such as measure theory, probability, functional analysis, algebra, etc. The main areas that we hope to cover are

  • graph homomorphisms and connection matrices
  • graphons as limits of dense graphs, including graphon versions of the Graph Regularity, Removal and (Inverse) Counting Lemmas, finite forcibility
  • flag algebras
  • measure-preserving systems as limits of bounded degree graphs, including the basics of Borel graphs, various notions of graph convergence (local, local-global, convergence on right), connections to LOCAL algorithms, group actions and statistical physics
  • analytic limits of other discrete structures (such as hypergraphs, permutations, etc)
  • applications to
    o extremal graph theory
    o quasi-randomness in combinatorics
    o property testing and parameter estimation in computer science
    o large deviation principles for some random graph models

Reading list

The module in 2021/22 will be based on the book by Laszlo Lovasz “Large Networks and Graph Limits”, Volume 60 of Colloquium Publications, American Mathematical Society, 2012 (available freely from the author's webpage), supplemented by selected topics from more recent research articles.