Hints and tips:
  • You may need to look up some unfamiliar terms in the title or description to get more of a sense of what is involved.
  • If the project has "No" in the "Current Availability:" field, it is already taken or not being offered this academic year but may be available again in future years.
  • The supervisor name links to a contact details webpage so, if you are interested, you can arrange to discuss this project or even propose a related topic of your own.
Level: MSci, MSc
Title: Szemerédi's regularity lemma
Supervisor:

Dr David Ellis

Research Area: Combinatorics
Description:

Szemerédi's regularity lemma is one of the most surprising and important results of modern Graph Theory, and has led to the resolution of a wide range of problems in combinatorics and number theory over the last forty years. Roughly speaking, it says that any graph can be partitioned into a small number of blocks, in such a way that the edges between most pairs of blocks are distributed in a highly uniform way.

The aim of this project would be to understand and present a proof of Szemerédi's regularity lemma, to give a survey of its applications, and to explain some of these in depth. It is slightly towards the harder end of the spectrum of MSci/MSc projects, but should be more rewarding as a result.

Further Reading:
Key Modules:

MTH6109 Combinatorics (helpful, but not essential)
Other Information:
Current Availability: Yes