Martingales and the Probabilistic Method

Nikita Lvov , Princeton University
Fine Hall 314

The probabilistic method is a powerful tool in many deterministic problems. In turn, the theory of martingales is a powerful tool for establishing probabilistic results. In this talk, I will describe these and use both to prove that most graphs of a given size have roughly the same chromatic number.