A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
The Probabilistic Method proves existence of graphs with desired properties by constructing random graphs and showing some realization has required properties, without explicitly building it. This powerful technique yields existence proofs for results difficult or impossible to establish constructively, revealing deep extremal results.
Work through a classical example like Erdős' lower bound on Ramsey numbers using the probabilistic method.
The probabilistic method proves existence without giving an explicit construction; a positive probability argument suffices to guarantee existence.
You know from expected value that if a random variable has a positive expected value, it must sometimes take positive values — and conversely, if it must be at least as large as some threshold on average, then there exist outcomes that meet or exceed that threshold. The probabilistic method, introduced by Paul Erdős, weaponizes this simple observation to prove the existence of graphs with remarkable properties. The strategy: define a probability space over graphs, show that some graph in this space has the desired property with positive probability, and conclude such a graph must exist. You never have to build it.
The cleanest introduction is Erdős's lower bound on Ramsey numbers. The Ramsey number R(k, k) is the smallest n such that any 2-coloring of the edges of the complete graph Kₙ contains a monochromatic clique of size k — a set of k vertices all connected by the same color. Proving R(k, k) is large (i.e., that you need many vertices before a monochromatic clique is forced) is where the probabilistic method shines. Color each edge of Kₙ red or blue independently with probability 1/2 each. The expected number of monochromatic k-cliques can be computed: there are C(n, k) subsets of k vertices, and each is monochromatic with probability 2 × (1/2)^C(k,2) = (1/2)^(C(k,2)−1). If the expected number of monochromatic k-cliques is less than 1, then there must exist some coloring with *zero* monochromatic k-cliques — and that coloring witnesses R(k, k) > n.
The deeper version uses the linearity of expectation and a union bound to handle more complex properties. Often the argument proceeds: (1) randomly construct a graph or coloring, (2) compute the expected value of some "bad event" count, (3) show the expected count is less than 1 (or less than the expected count of "good" events), (4) conclude a configuration exists with no bad events. The key insight is that you don't need to identify which random outcome works — you only need the expected value argument to force existence.
What makes the probabilistic method feel almost magical is that it produces non-constructive existence proofs for highly structured objects. Erdős proved that graphs with high girth (no short cycles) and high chromatic number (needing many colors) exist — objects that seem contradictory because cycles and colorability are usually linked. A random sparse graph, it turns out, achieves both properties simultaneously with positive probability. In many cases, decades passed between probabilistic existence proofs and the first explicit constructions, and in some cases explicit constructions are still unknown. The method has become one of the most powerful tools in combinatorics and theoretical computer science.