The Probabilistic Method Introduction

The probabilistic method is now a working tool far outside Ramsey theory. In extremal graph theory, it produces lower bounds on the size of graphs avoiding fixed substructures, and gives non-constructive existence proofs for graphs with high girth and high chromatic number simultaneously, a result that no known explicit construction achieved for decades. In coding theory, the Gilbert–Varshamov bound on error-correcting codes is proved by a nearly identical expectation/deletion argument over random codes. In theoretical computer science, probabilistic existence proofs directly inspired randomized algorithms; a randomized algorithm can often be seen as "sampling" from the same distribution used in an existence proof, and derandomization techniques (conditional expectations, pairwise independence) aim to convert such proofs into efficient constructions. In statistics and machine learning theory, concentration inequalities (Chernoff/Hoeffding bounds) that refine the crude expectation argument underlie generalization bounds and random projection methods (e.g. the Johnson–Lindenstrauss lemma, itself proved probabilistically). In spectral graph theory, the tension between random constructions and explicit algebraic ones (Ramanujan graphs, expander families) echoes the same theme explored here: randomness is easy to analyze in expectation, while explicit constructions matching probabilistic bounds are often much harder to find, a story that continues directly into Introduction to Spectral Graph Theory.

:::quiz[If $X$ is a nonnegative integer-valued random variable with $\mathbb{E}[X] = 0.7$, which conclusion is justified?]

• $X(\omega) = 0$ for every outcome $\omega$
• $X(\omega) < 1$ for every outcome $\omega$
• There exists at least one outcome $\omega$ with $X(\omega) = 0$ ✓
• $\Pr[X \ge 1] = 0.3$ exactly

:::quiz[In the Ramsey coloring model on $K_n$, what is $\Pr[A_S]$ for a fixed $k$-subset $S$, where $A_S$ is "$S$ is monochromatic"?]

• $2^{-\binom{k}{2}}$
• $2^{1-\binom{k}{2}}$ ✓
• $\binom{n}{k}2^{-\binom{k}{2}}$
• $1/2$

:::quiz[In the deletion method example with $k=4$, $n=9$, why could we find a coloring with at most $\lfloor \mathbb{E}[X]\rfloor$ monochromatic cliques?]

• Because $\mathbb{E}[X] < 1$ at $n=9$
• Because the average of an integer-valued random variable is always attained exactly by some outcome
• Because if every outcome exceeded $\lfloor \mathbb{E}[X]\rfloor$ the average would exceed $\mathbb{E}[X]$, a contradiction ✓
• Because deletion always removes exactly one vertex regardless of $m$

Ask the tutor: How does the second moment method (Chebyshev's inequality) sharpen the expectation argument when $\mathbb{E}[X]$ is large but the variance of $X$ is small?

Think of flipping a fair coin independently for every edge of the complete graph $K_n$: heads colors the edge red, tails colors it blue. This produces a uniformly random $2$-coloring of $E(K_n)$. Now ask: what is the chance that some specific set of $k$ vertices forms a monochromatic clique, all-red or all-blue? Each of the $\binom{k}{2}$ edges among those vertices must independently match in color, an event of probability $2 \cdot 2^{-\binom{k}{2}}$ (the factor $2$ accounts for "all red" or "all blue"). There are $\binom{n}{k}$ possible $k$-subsets, so by summing over subsets (linearity of expectation, no independence needed between different subsets), the expected number of monochromatic $k$-cliques is

If this quantity is less than $1$, then it is impossible for every outcome to have $X \ge 1$; some coloring must achieve $X = 0$. That coloring has no monochromatic $K_k$ at all, and its mere existence forces the Ramsey number $R(k,k)$ to exceed $n$. Nobody ever produces this coloring explicitly, we only prove it cannot fail to exist. The picture below shows the tension between $\binom{n}{k}$ (growing polynomially once $k$ is fixed, but here $k$ grows with $n$) and $2^{-\binom{k}{2}}$ (decaying doubly-exponentially in $k$), and where their product first dips below $1$.

Example 1: A concrete threshold, $k = 5$. We compute exactly when the expectation argument certifies $R(5,5) > n$. Here $\binom{k}{2} = \binom{5}{2} = 10$, so the exponent is $1 - 10 = -9$, and the condition is

We tabulate $\binom{n}{5}$ for small $n$:

At $n = 11$: $\binom{11}{5} \cdot 2^{-9} = 462/512 \approx 0.902 < 1$. At $n=12$: $792/512 \approx 1.547 > 1$. So the expectation argument, using the union-bound-style count of all $k$-subsets, certifies existence of a $2$-coloring of $K_{11}$ with no monochromatic $K_5$, hence

(The true value $R(5,5)$ is known only to lie between $43$ and $48$ as of current knowledge; our bound is far from tight but was obtained with zero combinatorial construction, only arithmetic.) This illustrates that the expectation argument is a lower bound technique: it never claims tightness, only existence past a computed threshold.

Example 2: The deletion method with $k = 4$, sharpening the raw bound. Sometimes $\mathbb{E}[X]$ is not below $1$, yet is still small compared to $n$, and we can improve the bound by deleting vertices. Take $k = 4$, so $\binom{k}{2} = 6$ and $\Pr[A_S] = 2^{1-6} = 2^{-5} = 1/32$. Try $n = 9$: $\binom{9}{4} = 126$, so $\mathbb{E}[X] = 126/32 = 3.9375$. This exceeds $1$, so the raw expectation argument alone gives no conclusion at $n=9$ (indeed, one checks separately that the raw threshold for $k=4$ is $n=8$, since $\binom{8}{4}=70$, $70/32 = 2.1875>1$ as well — so actually already at $n=8$ the plain expectation argument fails; the true threshold is lower). Let us instead demonstrate the deletion method precisely at $n=9$, to see how far it can push things when raw expectation exceeds $1$. We know $\mathbb{E}[X] = 3.9375$ at $n = 9$ for $k=4$. By definition of expectation as an average, there exists some coloring $\chi$ of $K_9$ with

(since if every coloring had $X \ge 4$, the average would be at least $4 > 3.9375$; more precisely there exists $\chi$ with $X(\chi) \le \mathbb{E}[X]$, and since $X$ is integer-valued, $X(\chi) \le \lfloor 3.9375 \rfloor = 3$). Fix such a $\chi$ with $X(\chi) = m \le 3$ monochromatic $K_4$'s. From each of these $m$ monochromatic $4$-cliques, delete one vertex (choosing, say, the lowest-indexed vertex in each clique; if cliques share vertices, one deletion may destroy several at once, only helping us). This removes at most $m \le 3$ vertices, destroying every monochromatic $K_4$ (since a $4$-clique with a vertex removed becomes a $3$-clique, no longer a $K_4$). The resulting coloring lives on at least $9 - 3 = 6$ vertices and has no monochromatic $K_4$. Hence $R(4,4) > 6$, i.e. $R(4,4) \ge 7$. This is weaker than the true value $R(4,4) = 18$, and in fact weaker than what the raw expectation argument gives at a smaller $n$ directly (one should check $n=7$: $\binom{7}{4} = 35$, $\mathbb{E}[X] = 35/32 \approx 1.09$, still just above $1$; at $n = 6$: $\binom{6}{4}=15$, $\mathbb{E}[X] = 15/32 < 1$, so the raw argument alone already gives $R(4,4) > 6$ directly). This comparison is itself instructive: the deletion method is most valuable exactly when the raw expectation is a little too large for the plain argument to apply outright but still small relative to $n$, letting us trade a few deleted vertices for a clean bound; for very small, explicit $k$ the raw bound can already be optimal among these elementary techniques, and deletion earns its keep at larger $k$ or in denser settings (e.g. hypergraph Ramsey numbers, or extremal set systems) where recomputing the raw threshold by hand is not as immediate.