Probabilistic methods in combinatorics

Summary

The 'probabilistic method' is a fundamental tool in combinatorics. The basic idea is as follows: to prove that an object (for example, graph) with certain properties exists, it suffices to prove that if the object is chosen at random, then it has the desired properties with positive probability.

Content

Keywords

probabilistic method, random graphs, concentration inequalities, expected value, variance

Learning Prerequisites

Recommended courses

Graph theory (MATH-360)

Important concepts to start the course

Familiarity with basic concepts of probability theory and graph theory are essential for this course. In particular, the student should be comfortable with the following notions from these subjects:

• random variable
• independence
• expectation
• variance, covariance
• complete graph
• subgraph
• paths, trees, cycles
• clique, independent set
• chromatic number

The first exercise class will be devoted to recalling the necessary background in probability theory and graph theory.

Learning Outcomes

By the end of the course, the student must be able to:

• Apply the probabilistic method to solve problems
• Choose which version of the method will be suited to the problem
• Prove the main results of the course
• Modify the main proofs if needed, to prove similar results

Teaching methods

In-person lectures + in-person exercise classes covering weekly exercise sheets.

Expected student activities

The students are expected to attend the lectures and the exercise classes. In addition, they are expected to attempt the problems on the exercise sheets and to submit their solutions of a selected subset of the exercises for grading.

Assessment methods

Written final exam

Supervision

Resources

Bibliography

Noga Alon and Joel H. Spencer. The probabilistic method. John Wiley & Sons, 2016.

Notes/Handbook

Lecture notes will be provided.

Moodle Link

• https://go.epfl.ch/MATH-467