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 the existence of objects with certain properties by showing that a random object has those properties with positive probability. It often provides nonconstructive proofs and lower bounds that can be stronger than constructive approaches.
The probabilistic method is a proof technique, not an algorithm. Its core logic is deceptively simple: if you define a random process over a collection of objects and show that the probability of some property P is strictly positive, then at least one object in the collection must have property P. You haven't constructed that object — you've only proven it exists. This nonconstructive character is the method's defining feature and also its most counterintuitive aspect.
From your study of the probabilistic method in graphs, you already know this idea in action. The classic tournament argument runs: randomly orient each edge of the complete graph Kₙ, then compute the expected number of vertices that beat all others. If this expectation is less than 1, there is not always a dominating vertex — so most tournaments lack one. Conversely, to show a combinatorial structure exists, you pick a random construction, compute the expected number of "bad" configurations using linearity of expectation, and show that expectation is less than 1. That forces the probability of zero bad configurations to be positive, so a good structure exists. Linearity of expectation is the engine here: E[X₁ + X₂ + ··· + Xₙ] = E[X₁] + ··· + E[Xₙ], even when the Xᵢ are dependent.
In combinatorics, the method's power appears in Ramsey bounds. To show R(k,k) > n — meaning there exist 2-colorings of Kₙ with no monochromatic k-clique — randomly 2-color the edges of Kₙ independently. For any particular k-clique, the probability it is monochromatic is 2 · (1/2)^C(k,2) = 2^(1−C(k,2)). Summing over all C(n,k) cliques using linearity of expectation, the expected number of monochromatic k-cliques is C(n,k) · 2^(1−C(k,2)). If this is less than 1, then with positive probability there are zero monochromatic k-cliques — so such a coloring exists. This gives exponential lower bounds R(k,k) > 2k/2 that stood for decades without constructive matches.
The method pairs naturally with the Lovász Local Lemma for situations where bad events are locally sparse but not globally rare. Without it, you need the total expected number of bad events to be small; the Local Lemma only requires each bad event to have low probability and to interact with few others. Together, the basic probabilistic method and the Local Lemma form a toolkit for proving existence of combinatorial objects — error-correcting codes, hypergraph colorings, constraint satisfaction solutions — whose explicit construction often remains an open problem long after existence is established.