Prerequisite: An undergraduate course on graph theory and basic notions of discrete probability ( found in many undergraduate CS and math courses).
When applying a Probabilistic Method, we find or prove the existence of a structure with certain desirable properties by showing that a randomly chosen structure from an appropriate distribution has these properties with positive probability. Such an approach often allows us to resolve optimization problems which have proven impervious to attack by other methods. We will discuss two examples. The first is the application of the probabilistic method in graph colouring. The second is the theory of Rapidly Mixing Markov Chains.
The course mark will be 25% assignments, 75% take home exam,
The text for the first half of the course
The first assignment is available on the assignment page which you can
The second assignment is available on the assignment page which you can
access via the announcements page.
Here is a chapter on Rapidly Mixing Markov Chains written by Mark Jerrum andAlisdair Sinclair