Nima Amini: The probabilistic method

The probabilistic method is a neat established technique in combinatorics (and other areas) for proving the existence of an object with prescribed properties. As is often the case in mathematics, constructively exhibiting a sought object can be difficult since one may be looking for a needle in a haystack (or in some cases even the hay in the haystack). In contrast to conventional non-constructive existence proofs which may commonly rely on contradiction or a non-constructive axiom, the method works under the following paradigm: If we can show that the prescribed object exists with positive probability under random selection, then the object must exist with certainty. We will cover why this seemingly trivial viewpoint can be useful and apply the technique to solve some combinatorial problems, after which we will state (and prove if time permits) the Lovász local lemma which is one of the main tools in applying this principle.