Level: BSc, MSci, MSc
Title: The probabilistic method in combinatorics
Supervisor:

Dr Robert Johnson
Research Area: Combinatorics
Description:

The Ramsey number R(k,k) is the smallest n with the property that however the edges of the complete graph Kn are 2-coloured there must be a monochromatic copy of Kk. Erdos gave a lower bound for R(k,k) by considering a random colouring and noting that provided the expected number of monochromatic copies of Kk is less than 1 there must be some graph with no monochromatic copies of Kk. This was one of the earliest and most striking uses of a probabilistic argument in combinatorics. Since then the probabilistic method has become a very well developed and important technique. There are numerous (more or less sophisticated) probabilistic techniques and combinatorial applications that could be explored in this project.
Further Reading:

N. Alon and J. H. Spencer, The Probabilistic Method. Wiley, New Jersey, 1992.
Key Modules:

MTH5121 Probability Models (desirable)

MTH6109 Combinatorics (desirable)
Other Information:
Current Availability: Yes