The probabilistic method is a name given to a method of proof and reasoning used in combinatorics, an area of mathematics concerned with discrete structures such as graphs (those with vertices and edges, not graphs of functions). The method was pioneered by Hungarian mathematician Paul Erdős in the 1940s. In essence, the idea is to prove that some combinatorial object of interest (typically a graph with certain properties) exists, without having 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 an independent field in its own right, called 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 2H Probability are essential.
3H Probability and/or 4H Stochastic Processes are not necessary 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 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.
Get in touch if you have any questions!