2007 – Topics on the probabilistic method

organizer Nicolas Macris
office INR 134
phone 38114
email nicolas.macris@epfl.ch

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