CO 648The 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 introduces the fundamental techniques and gives numerous applications in a wide variety of areas, including graph theory, combinatorics, number theory, geometry, optimization, randomised algorithms, and information theory. In particular, normally the following topics are discussed: method of the first moment; Chebyshev’s inequality; alterations; the Lovasz local lemma; correlation inequalities; exponential concentration inequalities; applications.