The Probabilistic Method

Advanced lecture course Summer Semester 2009

The Probabilistic Method was invented by Paul Erdõs in the 1950's and since then it has found widespread applications to a number of areas of Mathematics and Computer Science, such as the analysis of algorithms, Combinatorics and Graph Theory and Number Theory. The idea which lies at its very heart is the following: if one wants to prove the existence of a certain structure or property, then one can construct a probability space and show that the structure or the property in question occurs with positive probability. It turns out that this simple idea is powerful enough to show the existence of complicated structures in a very elegant and concise way. In this course, we will introduce the method and cover a number of classical applications of it. We will also interpret such results into efficient algorithms and develop the methodology of derandomization. However, as we interpret the term "Probabilistic Method" in a broad sense, we will also cover some related topics as Markov chains, simple random walks on graphs, applications to Information Theory and a short introduction to pseudorandomness and the regularity lemma.

Instructors:	Nikolaos Fountoulakis, Konstantinos Panagiotou and Anna Huber (Teaching assistant)
Time & room:	Tuesdays 16-18 in E1.4 room 0.24 (Lectures) & Wednesdays 10-12 in E1.4 room 333 (Rotunda 3rd floor) (Problem sessions).
Start:	Tuesday, April 21, 2009
Credit:	This lecture is an advanced course with integrated exercise sessions (2+1).
Prerequisites:	Basic knowledge of discrete probability, graph theory and algorithms.
Course Material:	Most of the topics we will cover can be found in The Probabilistic Method by N. Alon and J. Spencer (Wiley, 2000). We will also cover a few topics from M. Mitzenmacher and E. Upfal, Probability and computing. Randomized algorithms and probabilistic analysis., Cambridge University Press, 2005. B. Bollobás, Graph Theory , Springer, 1998.

Course Contents:

Introduction to the Probabilistic Method with some applications to Graph Theory.
Linearity of expectation and applications: independent sets in graphs, Ramsey numbers, the analysis of Quicksort.
Derandomization techniques.
The Lovász Local Lemma and some applications.
The derandomization of the Lovász Local Lemma.
The second moment method with applications to the coupon collector problem, the number of prime factors of integers, ball-in-bins allocation problems as well as the Weierstrass approximation theorem.
A randomized algorithm for finding the median.
Some Markov chains for the satisfiability problem.
Chernoff bounds, their proofs and applications.
Expander graphs.
Concentration inequalities for martingale sequences; applications.
Janson's inequality and applications to graph colouring and subgraph count.
Random walks on graphs, basic identities.
Application of the Probabilistic Method to Information Theory, Shannon's Theorem.
Introduction to pseudorandomness and Szemerédi's regularity lemma.