MSc Pure Mathematics and Mathematical Logic / Course details

Graph theory is the study of one of the most simple objects in mathematics: a finite set of vertices with edges between them. Despite their simplicity, the study of graphs is a broad and deep area of modern mathematics, with many recent results and open problems still unanswered. Results about graphs are also widely applicable to many other areas of pure and applied mathematics.

In this course we will take a tour of some highlights of graph theory, and investigate applications to several questions in number theory (in particular additive combinatorics).

We begin with Ramsey theory, which studies how structure emerges inevitably from colouring large graphs. We will then discuss planar graphs, which can be drawn in the plane without crossing edges, and apply these concepts to the study of point-line incidence results in elementary geometry and the interplay between addition and multiplication.

We then turn to colouring results, which explore how graphs can be coloured (in either vertices or edges) to avoid collisions, including a proof of the 5 colour theorem (a weaker variant of the infamous 4 colour theorem).  

Finally, we conclude with one of the most powerful techniques in modern graph theory: regularity, which says that any graph can be decomposed into a small number of regular parts. This has many applications, and we will investigate how it can lead to deep results about counting triangles in arbitrary graphs and finding three-term arithmetic progressions in sets of integers. 

The unit aims to: explore some of the main areas of graph theory, including Ramsey theory, graph colouring, and graph regularity, and apply these to obtain results in number theory.

On the successful completion of the course, students will be able to:

1. Define Ramsey numbers and calculate or estimate these for specific families of graphs.
2. Prove properties of planar graphs and apply them to graph colouring and crossing numbers of graphs.
3. Use graph theory to bound the number of incidences between points and lines and apply these bounds to prove results in number theory.
4. Prove results about vertex and edge colourings of graphs, including properties of the chromatic polynomial, and use these to explore colourings of specific families of graphs.
5. Define and use graph regularity to show that large graphs can be decomposed into regular parts and to prove counting and removal lemmas for specific graphs.
6. Apply graph counting and removal lemmas to prove results in number theory.

Syllabus:

Ramsey theory and Ramsey numbers [4 lectures]  

Planar graphs and crossing numbers [2 lectures]

Applications of planarity to incidence results and the sum-product theorem [2 lectures]

Vertex colouring and the chromatic polynomial [4 lectures]

Edge colouring and Vizing’s theorem [3 lectures]

Szemeredi’s regularity lemma [3 lectures]

Triangle removal lemma and Roth’s theorem [4 lectures] 

For problem sheets (every 2 weeks), feedback will be delivered on returned scripts within a week of submission.

B. Bollobas, Modern Graph Theory, Springer 1998

R. Diestel, Graph Theory, Springer 2025

Y. Zhao, Graph Theory and Additive Combinatorics, Cambridge University Press 2023