Probabilistic combinatorics is a relatively new area of mathematics, pioneered by the Hungarian mathematician Paul Erdős in the 1940s (that's new for maths!), who applied ideas and techniques from probability theory to the study of discrete objects (trees, graphs, partitions, permutations, ...).
Erdős' methods became known as 'the probabilistic method'. The idea behind the method is that to find some combinatorial object of interest (for example, a graph with some particularly nice/interesting properties), one can create some simple random experiment for which the likely outcome is the object of interest. As such, one discovers that the object must exist, without needing to explicitly construct it! The beauty of the method is that these "existence proofs" are often very elegant and concise, in contrast to their "constructive" counterparts.
In its most basic form, the probabilistic method can be viewed as an elementary counting argument; but its real power comes to light when viewed probabilistically, as this allows us to employ well-established theory and concepts from probability theory, such as expectation, variance, as well as more sophisticated tools: e.g., martingales, concentration inequalities.
The method was first used by Erdős to prove a lower bound on the Ramsey number R(k,k). For positive integers k and l, the Ramsey number R(k,l) is defined as the minimum positive integer n such that any red/blue colouring of the edges of the complete graph Kn either contains an all-red Kk as a subgraph, or an all-blue Kl as a subgraph. For example, it is not too difficult to check that R(3,3) = 6.
Since then, it has seen many applications to other areas of mathematics and computer science, as well as evolving into the much broader area known as probabilistic combinatorics. In this project you will have the opportunity to study some of these methods and their applications. Possible topics to explore include, but are not limited to:
to name but a few.
Discrete Mathematics and (Probability II or Markov Chains II) are essential prior modules.
Stochastic Processes III is not a necessary companion module but may be helpful with understanding some of the more advanced probabilistic techniques/topics.
An excellent resource is the book The Probabilistic Method by Alon and Spencer, 2016. The University Library has some physical copies and you may be able to find an electronic copy by searching online.
You can also search online for "probabilistic combinatorics", "probabilistic method" and the other phrases above for more information.
If you need a reminder of some of the graph-theoretic concepts from Discrete Mathematics have a look at Modern Graph Theory, B. Bollobás, 1998, or Graph Theory, R. Diestel, 2016, free preview version available online.
The life and work of Paul Erdős was the topic of discussion in the BBC radio show In Our Time in 2023.
Get in touch if you have any questions!