Probabilistic Method

The probabilistic method is one of the most powerful and versatile techniques in modern combinatorics. Instead of constructing combinatorial objects directly, we use randomness to prove that such objects must exist. This approach, pioneered by Erdős, has reshaped entire areas of mathematics by providing elegant proofs of existence theorems and by revealing deep connections between probability and discrete structures.

This course serves as a rigorous introduction to probabilistic combinatorics. We will develop the foundational tools of the subject, focusing on core methods such as expectation and linearity of expectation, alteration arguments, second-moment techniques, and the Lovász Local Lemma. Along the way, we will study fundamental applications in Ramsey theory, graph coloring, hypergraph constructions, and coding theory.

While our primary guide will be material corresponding to the early chapters of The Probabilistic Method by Alon and Spencer, the course will emphasize problem-solving and the creative use of probabilistic reasoning. Students will learn how to translate combinatorial problems into probabilistic language, how to select the right tools for analysis, and how randomness can be derandomized into explicit constructions.

By the end of the course, students will not only master the central methods of probabilistic combinatorics but also gain insight into how randomness has become an indispensable part of modern mathematics, computer science, and related fields.

Lecture 1. Proposition 1.1.1 (pag. 3), Theorem 1.2.1 (pag. 6), Theorem 1.2.2 (pag. 6), Lemma 1.2.3 (pag. 8).

Lecture 2. Proposition 1.3.1 (pag. 9), Theorem 1.3.2 (pag. 10), Theorem 1.3.3 (pag. 11).

Week 1. Problems 1.7.1, 1.7.2

1. Paul Erdős and Joel Spencer, Probabilistic Methods in Combinatorics [Link]
2. Extremal and Probabilistic Combinatorics by N. Alon and M. Krivelevich [link]
3. Discrete Analysis Journal [link]