First-year graduateDiscrete MathematicsPlanned

The probabilistic method

Proving existence by showing that a random object has the desired property with positive probability: Erdős's lower bound for Ramsey numbers, linearity of expectation, the second-moment method, the Lovász local lemma and concentration inequalities.

math.discrete.probabilistic-method

Show everything needed to reach this topic

The lesson for this topic has not been written yet. The outline below is part of the curriculum map and has not been reviewed.

Builds on

Graph theory Probability theory

Required prerequisites, all the way down: 44

You will learn to

Prove Erdős's bound R(k, k) > 2^(k/2) for k ≥ 3 using a random colouring.
Use linearity of expectation and deletion arguments to prove existence results.
Apply the Lovász local lemma and Chernoff bounds.

Definition

First-moment method: if X takes non-negative integer values and E[X] < 1, then P(X = 0) > 0.
Lovász local lemma (symmetric form): if each of a collection of bad events has probability at most p and is mutually independent of all but at most d of the others, and ep(d + 1) ≤ 1, then with positive probability none of the bad events occurs.

Theorem

R(k, k) > 2^(k/2) for every k ≥ 3 (Erdős, 1947).
There are graphs with arbitrarily large girth and arbitrarily large chromatic number (Erdős, 1959).

Common misconceptions

Thinking a probabilistic existence proof gives an efficient construction; explicit constructions are often unknown.

Optional discoveries

Computational complexity Derandomisation asks when random constructions can be replaced by efficient deterministic ones; the algorithmic local lemma of Moser and Tardos is one success.