MA9M2 Topics in Combinatorics

Introductory description

This is a topics course, whose specific content will vary from year to year to address material of particular interest in the current year. The general aim is to present some selected topics and methods of importance in modern combinatorics and graph theory, especially those that also may be of general significance and have potential applications to other fields.

Module aims

Outline syllabus

This is an indicative module outline only to give an indication of the sort of topics that may be covered. Actual sessions held may differ.

This module in 2021-22 will concentrate on the emerging theory of the limits of discrete structures which, besides of being of independent interest, builds a 2-way bridge connecting combinatorics to other fields such as measure theory, probability, functional analysis, algebra, etc. The main areas will be

• 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 large deviation principles for various random graph models
  o property testing and parameter estimation in computer science

Learning outcomes

By the end of the module, students should be able to:

• By taking this module, PhD students will be exposed to some important developments in combinatorics and graph theory including key open problems, acquire the background and understanding needed in order to be able to read research papers on the covered topics, and be prepared to conduct their own research in these areas.

Indicative reading list

Reading lists can be found in Talis

Subject specific skills

Transferable skills: by default – nothing to if happy with this

• sourcing research material
• prioritising and summarising relevant information
• absorbing and organizing information
• presentation skills (both oral and written)

Transferable skills

• sourcing research material
• prioritising and summarising relevant information
• absorbing and organizing information
• presentation skills (both oral and written)