The Probabilistic Method

The probabilistic method, pioneered by Paul Erdos, proves the existence of combinatorial objects with desired properties by showing that a randomly chosen object has the property with positive probability. This non-constructive technique has become one of the most versatile tools in combinatorics.

Basic Method

Definition7.1Probabilistic Existence Argument

To show that a combinatorial structure with property $P$ exists, define a probability space on the set of all candidate structures and prove $\Pr[P] > 0$ . This guarantees existence without providing an explicit construction.

Definition7.2Random Graph $G(n, p)$

The Erdos-Rényi random graph $G(n, p)$ is the probability space of graphs on $n$ labeled vertices where each edge is included independently with probability $p \in [0, 1]$ . For $p = 1/2$ , the model assigns equal probability $2^{-\binom{n}{2}}$ to each graph on $n$ vertices.

ExampleErdos's Ramsey Lower Bound

$R(k, k) > n$ for $n = \lfloor 2^{k/2} \rfloor$ . Proof: In $G(n, 1/2)$ , for any $k$ -subset $S$ , the probability that $S$ is a clique or independent set is $2 \cdot 2^{-\binom{k}{2}}$ . By the union bound: $\Pr[\exists \text{ monochromatic } K_k] \leq \binom{n}{k} \cdot 2^{1-\binom{k}{2}} < \frac{n^k}{k!} \cdot 2^{1 - k(k-1)/2}.$ For $n = \lfloor 2^{k/2} \rfloor$ , this is less than 1. So a 2-coloring of $K_n$ without monochromatic $K_k$ exists.

First Moment Method

Definition7.3First Moment Method

If $X$ is a non-negative random variable, then $\Pr[X \geq 1] \leq \mathbb{E}[X]$ (Markov). Contrapositively, if $\mathbb{E}[X] < 1$ , then $\Pr[X = 0] > 0$ . For "deletion" arguments: if $\mathbb{E}[X]$ is small, one can delete few elements to achieve $X = 0$ .

RemarkAlteration Method

The alteration (or deletion) method starts with a random structure, then modifies it to achieve the desired property. For instance, to find a large independent set in a graph, take a random subset $S$ of vertices, then delete one vertex from each edge within $S$ . The expected number of surviving vertices provides a lower bound on $\alpha(G)$ .