The Probabilistic Method

Contact: Ghid Maatouk
Room: BC 128
Tel: 021-693-12-05
Email: ghid [dot] maatouk [at] epfl [dot] ch

In this project, you will learn about the probabilistic method, a powerful tool for proving non-constructively the existence of certain structures. You will study basic probabilistic tools such as large deviation results, and apply them to understand proofs of several results such as Ramsey theorems, lower bounds on the independence number/clique number of graphs, existence of tournaments, and other results.

Prerequisites: basic probability.

Méthode probabiliste et lemme local de Lovász