CO 448The Probabilistic Method

The probabilistic method is a collection of proof techniques to show the existence of a combinatorial structure by showing a random element in an appropriate probability space has the desired structure with a positive probability. The course will introduce the fundamental techniques and give numerous applications in a wide variety of areas, including graph theory, combinatorics, number theory, geometry, optimization, randomized algorithms, and information theory. In particular, normally the following topics will be discussed: method of the first moment, Chebyshev’s inequality, alterations, the Lovasz local lemma, correlation inequalities, exponential concentration inequalities, and applications.