2007 – Topics on the probabilistic method

organizer Nicolas Macris
office INR 134
phone 38114
email [email protected]

meetings: mondays 12h15 – 13h15 in room INR 113


This semester we will study the “probabilistic method” through a selection of special topics and examples from the two books:

“Ten Lectures on the Probabilistic Method”, by Joel Spencer
“The Probabilistic Method”, by Noga Alon and Joel Spencer

The method can be briefly described as follows: to prove the existence of certain combinatorial structures one constructs an appropriate probability space and shows that a randomly chosen element has the desired property with positive probability. This kind of ideas, initialy introduced by Erdos, have become a powerful tool in combinatorics, discrete mathematics, computer science.

We will meet on a weekly basis for presentations of 1h between 12h15 and 13h15, starting on monday march 19. Participants are encouraged to bring their lunch.

Evolving schedule

speaker date topic
Shrinivas Kudekar March 19 Ramsey numbers
Amin Karbasi March 26 Lovasz local lemma
Jeremie Ezri April 2 Janson inequalities
April 9 easter holiday
Jeremie Ezri April 16 applications of Janson inequalities
Iryna Andriyanova April 23 concentration, martingales
Satish Korada April 30 Talagrand inequality
Satish Korada May 7 Talagrand continued
Mahdi Cheraghchi May 14 evolution of random graphs
Mahdi Cheraghchi May 21 evolution of random graphs cont
May 28 holiday
Shrinivas Kudekar June 4 zero-one laws
June 11