Probabilistic method

Remarks

Erdős' bound for diagonal Ramsey numbers is an example. Let $k \ge 3$ and $n = \floor{2^{k/2}}$, and colour each edge of the complete graph $K_n$ red or blue independently with probability $1/2$. The expected number of monochromatic copies of $K_k$ is $\binom{n}{k} 2^{1 - \binom{k}{2}}$, and this is less than $1$. So some colouring has no monochromatic $K_k$, and the Ramsey number satisfies $R(k, k) > \floor{2^{k/2}}$. An argument that only shows that the event has probability at least $0$ is not a proof by this method. Step 2 fails there, and an event of probability $0$ may be empty. The method also applies to infinite probability spaces, with the same conclusion that an event of positive probability is nonempty.