Combinatorics and discrete mathematics

The probabilistic method

Proves that an object with a desired property exists by showing a random construction has positive probability of having it.

IntuitionProving existence without building anything

Sometimes the fastest way to show that a mathematical object with a strange, desirable property exists is not to build one by hand, but to build a random one and compute the odds. If a random construction has the desired property with probability greater than zero, then at least one instance of it must exist somewhere among all the possible outcomes — even if nobody can point to it directly. This is the probabilistic method: turn an existence question into a question about averages and probabilities.

The complete graph

K_5

\binom{5}{2}=10

edges, each independently colored red or blue with probability

1/2

. This is the random object at the heart of Erdős's argument: instead of hand-picking one 2-coloring of

K_n

, we imagine tossing a coin for every edge.

UndergraduateThe first-moment method

Definition: Random 2-coloring and monochromatic clique

Color each of the $\binom{n}{2}$ edges of $K_n$ independently red or blue, each with probability $1/2$ . For a set $S$ of $k$ vertices, say $S$ is monochromatic if every edge inside $S$ got the same color. Let $X$ be the total number of monochromatic $k$ -subsets of $K_n$ .

X = \sum_{S \subseteq V,\ |S|=k} \mathbb{1}[A_S]

Here $X$ sums an indicator over all $\binom{n}{k}$ possible choices of $S$ . Since each of the $\binom{k}{2}$ edges inside $S$ is colored independently, $S$ is monochromatic (all red, or all blue) with probability $2^{1-\binom{k}{2}}$ . Linearity of expectation — which holds even though the events for overlapping sets $S$ are far from independent — lets us add these probabilities directly to get $\mathbb{E}[X]$ .

\mathbb{E}[X] = \binom{n}{k}\,2^{1-\binom{k}{2}}

Some classical results proved by the probabilistic method
Result	What is shown to exist	Technique
Ramsey number lower bound	a 2-coloring of $K_n$ with no monochromatic $K_k$	First-moment method
Graph cuts (Max-Cut)	a bipartition crossing at least $m/2$ edges	Linearity of expectation
Independent sets (Turán-type)	an independent set of size at least $n/(d+1)$	Deletion method
Hypergraph 2-colorability	a 2-coloring with no monochromatic edge	Lovász Local Lemma

UndergraduateKey theorems

Theorem: Linearity of expectation for indicator sums

For any events $A_1,\dots,A_m$ in a probability space (not necessarily independent), if $X = \sum_{i=1}^m \mathbb{1}[A_i]$ counts how many of them occur, then $\mathbb{E}[X] = \sum_{i=1}^m \Pr[A_i]$ .

Why is it true?

It lets us compute the average of a count by adding up individual probabilities one at a time, without ever worrying about how the events interact with each other — the single most useful shortcut in the probabilistic method.

Proof

Write $X = \sum_{i=1}^m \mathbb{1}[A_i]$ where $\mathbb{1}[A_i]$ is $1$ if $A_i$ occurs and $0$ otherwise. Expectation is itself defined as a sum (or integral) over outcomes weighted by their probability, and this sum is always additive over a finite list of random variables — this is true regardless of whether the variables are independent, since additivity of expectation never uses independence, only that we are summing the same underlying probability measure.

Formally, $\mathbb{E}[X] = \mathbb{E}\left[\sum_{i=1}^m \mathbb{1}[A_i]\right] = \sum_{i=1}^m \mathbb{E}[\mathbb{1}[A_i]]$ by additivity of expectation over a finite sum of random variables.

Finally, for any indicator variable, $\mathbb{E}[\mathbb{1}[A_i]] = 1 \cdot \Pr[A_i] + 0 \cdot \Pr[\overline{A_i}] = \Pr[A_i]$ . Substituting this into the sum gives exactly $\mathbb{E}[X] = \sum_{i=1}^m \Pr[A_i]$ , with no assumption on how the $A_i$ relate to one another.

Theorem: Erdős's exponential lower bound for Ramsey numbers

For every integer $k$ $\ge 3$ , $R(k,k) > 2^{k/2}$ .

Why is it true?

As $k$ grows, the number of $k$ -subsets of an $n$ -vertex graph grows only polynomially in $n$ , but the chance that any particular subset is monochromatic shrinks doubly-exponentially in $k$ . Balancing these two rates shows the expected number of monochromatic cliques stays below $1$ even when $n$ is exponentially large in $k$ , which is far better than any bound anyone has managed to construct by hand.

Proof

Set $n = \lfloor 2^{k/2} \rfloor$ . From the first-moment computation above, $\mathbb{E}[X] = \binom{n}{k}\,2^{1-\binom{k}{2}}$ . If we show $\binom{n}{k}\,2^{1-\binom{k}{2}} < 1$ , then since $X$ only takes nonnegative integer values, some 2-coloring must achieve $X=0$ — otherwise $X \ge 1$ always, forcing $\mathbb{E}[X]\ge 1$ . A coloring with $X=0$ has no monochromatic $k$ -clique at all.

Bound the binomial coefficient by $\binom{n}{k} \le n^k/k!$ , and since $n \le 2^{k/2}$ we get $n^k \le 2^{k^2/2}$ . Substituting into the expectation formula, $\mathbb{E}[X] \le \dfrac{2^{k^2/2}\cdot 2^{1-\binom{k}{2}}}{k!}$ .

Simplify the exponent: $\dfrac{k^2}{2} + 1 - \dfrac{k(k-1)}{2} = 1 + \dfrac{k^2 - k^2 + k}{2} = 1 + \dfrac{k}{2}$ . So $\mathbb{E}[X] \le \dfrac{2^{1+k/2}}{k!}$ , and it suffices to show $k! > 2^{1+k/2}$ for every $k \ge 3$ .

Check this by induction on $k$ . Base case $k=3$ : $3! = 6$ and $2^{1+3/2} = 2^{2.5} \approx 5.657$ , and indeed $6 > 5.657$ . For the inductive step, suppose $k! > 2^{1+k/2}$ holds at some $k \ge 3$ . Then $(k+1)! = (k+1)\cdot k! > (k+1)\cdot 2^{1+k/2}$ , and since $k+1 \ge 4 > \sqrt2$ , this exceeds $\sqrt2 \cdot 2^{1+k/2} = 2^{1+(k+1)/2}$ , which is exactly the claim at $k+1$ . So $k! > 2^{1+k/2}$ holds for every $k \ge 3$ , which gives $\binom{n}{k}\,2^{1-\binom{k}{2}} < 1$ as needed.

Therefore a 2-coloring of $K_n$ with no monochromatic $k$ -clique exists, so $R(k,k) > n = \lfloor 2^{k/2}\rfloor$ . Since $\lfloor x\rfloor + 1 > x$ for every real $x$ , this gives $R(k,k) \ge \lfloor 2^{k/2}\rfloor + 1 > 2^{k/2}$ , which is exactly $R(k,k) > 2^{k/2}$ .

UndergraduateReal-World Applications and Worked Examples

The probabilistic method is a working tool in computer science, not just a pure-existence curiosity. Randomized algorithms routinely use the same first-moment argument to guarantee a good solution exists, then either search for it or output a random instance that is good with high probability — this underlies randomized approximation algorithms for network cuts, the design of error-correcting codes and pseudorandom generators, and frequency/channel assignment in wireless networks.

Example: Guaranteeing a large network cut

A data-center network is modeled as a graph with $m=17$ links between racks. Show that the racks can always be split into two groups so that at least $9$ links go between the groups (useful for load-balancing traffic across two halves of the network).

Solution

Randomly and independently assign each rack to group $A$ or group $B$ with probability $1/2$ each. For any fixed link $\{u,v\}$ , it crosses the groups exactly when $u$ and $v$ land in different groups, which happens with probability $2\cdot\tfrac12\cdot\tfrac12=\tfrac12$ (either $u\in A, v\in B$ or $u\in B, v\in A$ ).

Let $Y$ be the number of crossing links. By linearity of expectation over all $m=17$ links (regardless of how the links share endpoints), $\mathbb{E}[Y] = 17\cdot\tfrac12 = 8.5$ .

Since $Y$ is always a nonnegative integer, some particular assignment of racks to groups must achieve $Y \ge \lceil 8.5\rceil = 9$ — if every assignment gave $Y\le 8$ , the average could not reach $8.5$ . That assignment is the desired split.

Example: A guaranteed interference-free channel set (deletion method)

A wireless network has $n=40$ transmitters and $m=60$ pairs of transmitters that interfere with each other if both are active at once. Show that at least $10$ transmitters can be activated simultaneously with no interfering pair among them.

Solution

Model transmitters as vertices of a graph and interfering pairs as edges, so $n=40$ , $m=60$ , and the average degree is $d = 2m/n = 2\cdot60/40 = 3$ . We want an independent set (no edge inside it).

Pick a uniformly random ordering of all $n$ vertices, and keep a vertex $v$ if it appears earlier in the order than every one of its neighbors (a "local minimum"). If two kept vertices were adjacent, the later one in the order would have an earlier neighbor and could not have been kept — so the kept vertices always form an independent set $I$ .

A vertex $v$ of degree $d_v$ is kept exactly when it is first among itself and its $d_v$ neighbors in the random order, which happens with probability $1/(d_v+1)$ . By linearity of expectation, $\mathbb{E}[|I|] = \sum_v \dfrac{1}{d_v+1}$ , and since $x\mapsto 1/(x+1)$ is convex, this sum is minimized (by Jensen's inequality) when every $d_v$ equals the average degree $d$ , giving $\mathbb{E}[|I|] \ge \dfrac{n}{d+1}$ .

Plugging in the numbers, $\mathbb{E}[|I|] \ge \dfrac{40}{3+1} = 10$ . Since $|I|$ is an integer-valued random variable, some ordering must achieve $|I| \ge 10$ , giving the desired interference-free set of transmitters.

Research frontier as of 2026

The gap between the probabilistic lower bound $R(k,k) > 2^{k/2}$ and the best known upper bound remains one of the most famous open problems in combinatorics; in 2023, Campos, Griffiths, Morris and Sahasrabudhe gave the first exponential improvement to the classical upper bound in over 70 years, showing $R(k,k) \le 3.99^{k}$ via a refined random-coloring argument, but a large gap to the lower bound persists. On the tools side, the Lovász Local Lemma — a strengthening of the first-moment method for dependent bad events — now has efficient algorithmic versions (the Moser–Tardos algorithm, 2010) that actually construct the guaranteed object rather than merely proving it exists, and the hypergraph containers method (Balogh–Morris–Samotij and Saxton–Thomason, mid-2010s) extends probabilistic counting arguments to control the number of independent sets and other sparse structures in hypergraphs, driving current research in extremal and additive combinatorics.

Events $A_1, A_2, A_3$ (possibly dependent) each have $\Pr[A_i] = 0.3$ . Let $X = \sum_{i=1}^3 \mathbb{1}[A_i]$ count how many occur. What is $\mathbb{E}[X]$ ?

For $k=4$ , evaluate $\mathbb{E}[X] = \binom{n}{4}\cdot 2^{1-\binom{4}{2}}$ at $n=4$ . (Recall $\binom{4}{4}=1$ and $\binom{4}{2}=6$ .)

A network engineer models a network as a graph with $m=50$ links. Using the probabilistic method (random bipartition and linearity of expectation), what cut size can always be guaranteed?

The first-moment method shows $\mathbb{E}[X] < 1$ for the number of monochromatic $k$ -cliques under a random 2-coloring of $K_n$ . What can we correctly conclude?

References

Noga Alon, Joel H. Spencer (2016). The Probabilistic Method
Marcelo Campos, Simon Griffiths, Robert Morris, Julian Sahasrabudhe (2023). Towards fully exponential bounds for the diagonal Ramsey numbers · arXiv:2303.09521 [preprint, not peer-reviewed]
Reinhard Diestel (2017). Graph Theory