The probabilistic method is one of the most powerful and widely used
tools in modern Combinatorics. One of the main reasons for its rapid
development is the important role of randomness in theoretical computer
science and in statistical physics. The basic idea of the probabilistic
method can be described as follows: in order to prove the existence of
a combinatorial structure with certain properties, one constructs an
appropriate probability space and shows that a randomly chosen element
in this space has the desired properties with positive probability.
In the course we follow the monograph of Alon and Spencer and concentrate
on the methodology of the subject. We develop the classic tools (including
the first moment method, second moment method, alterations, the Local Lemma),
as well as more recent applications involving martingales and correlation
inequalities. If time permits we will see further applications in
theoretical computer science and geometry.
In our treatment we will place a special emphasis on the algorithmic point
of view.
The course will be followed with a seminar in the Summer semester of 2011.
Starting on October 4th, a 4-week MDS-predoc course will take place at
FU, with a topic (Differential Equation Method for Stochastic Processes)
highly relevant to the Probabilistic Method.
Interested students are encouraged to attend both.
The course is aimed at Masters students in Mathematics or Theoretical
Computer Science. Higher level Bachelor students can also take it
as an elective course.
The prerequisites are Probability I,
Discrete Mathematics I and II and a piece of mathematical maturity.