The Probabilistic Method
Winter Semester, 2010/11.


Instructor.

  • Tibor Szabó
  • Telephone: 75217
  • Office: 211.5, Arnimallee 3
  • Office hours: by appointment
  • Email: szabo at math dot fu-berlin dot de
  • Top

    Lectures.

  • Time: Tuesday, 12:30PM - 14:00PM
  • Location: 025/026, Arnimallee 6.
  • Exercises.

  • Time: Tuesday 14:15PM - 15:45PM.
  • Location: 025/026, Arnimallee 6.

    Exam.

  • Time: February 22nd (Tuesday) at 13:00.
  • Location: ?????
    Top

    Course Information.

    Essential administrative information about the course is HERE .
    Top

    Course Description.

    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.
    Top

    Prerequisites.

    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.
    Top

    Textbook.

  • N. Alon and J.H. Spencer, The Probabilistic Method, 3rd ed., 2008.
    Top

    Assignments.

    Assignment 1. and 2.
    Assignment 3.
    Assignment 4.
    Assignment 5.
    Assignment 6.
    Assignment 7.
    Assignment 8.
    Assignment 9.
    Assignment 10.
    Assignment 11.
    Assignment 12.