probabilistic lower bounds for Ramsey numbers

Probabilistic lower bounds for Ramsey numbers are the founding triumph of the probabilistic method and remain among its most striking demonstrations. The Ramsey number R(k, k) is the smallest n such that every two-colouring of the edges of the complete graph on n vertices contains a monochromatic clique on k vertices — a complete subgraph all of whose edges are the same colour. Ramsey's theorem guarantees R(k, k) is finite; the question is how large it is. A lower bound R(k, k) > n means there exists a two-colouring of the edges of K_n with NO monochromatic k-clique, i.e. a colouring that 'avoids order'. Exhibiting such a colouring explicitly is extraordinarily hard; the probabilistic method produces one almost for free.

Erdos's 1947 argument: colour each edge of K_n red or blue independently by a fair coin. For a fixed set of k vertices, the probability its C(k,2) edges are all the same colour is 2 times 2^(-C(k,2)) (all red or all blue). By the first moment method (union bound), the expected number of monochromatic k-cliques is at most C(n,k) * 2^(1 - C(k,2)). If this expected number is strictly less than 1, then with positive probability there are no monochromatic k-cliques, so a good colouring exists and R(k, k) > n. A short calculation shows the expectation is below 1 whenever n is at most about 2^(k/2) / e times a polynomial factor, giving R(k, k) > (1 + o(1)) (k / (e sqrt(2))) 2^(k/2). The deletion method sharpens the constant a little further by allowing a few monochromatic cliques and deleting one vertex from each.

The astonishing fact, and the reason this example is told first in every course, is the gap between knowledge and construction. The probabilistic bound 2^(k/2) was proved in two lines in 1947; the best explicit constructions of Ramsey colourings lagged exponentially behind for over sixty years, only recently approaching the random bound through deep work in pseudorandomness. The upper bound R(k,k) <= 4^k (Erdos-Szekeres) leaves the base of the exponential between sqrt(2) and 4 still undetermined — a famous open problem — and improving even the constant in the lower bound is hard. The honest caveat is that the method proves a colouring with no large monochromatic clique EXISTS but names none: it is a pure existence proof, and for decades no one could write down a single colouring matching what the random one achieves.