Probabilistic Method: Lower Bounds for Ramsey Numbers

One of the earliest and most influential applications of the probabilistic method in combinatorics was given by Paul Erdős in his 1947 paper Some Remarks on the Theory of Graphs. The argument is famous not because it is long or technically complicated, but because it introduced a powerful new way of proving existence. Instead of constructing a mathematical object explicitly, Erdős showed that if we choose an object randomly, then the probability that it has the desired property is positive. Therefore, such an object must exist.

The setting is Ramsey theory. The diagonal Ramsey number $R(k,k)$ is the smallest integer $N$ such that every red-blue coloring of the edges of the complete graph $K_N$ contains a monochromatic copy of $K_k$ . A monochromatic $K_k$ is a set of $k$ vertices such that every edge between them has the same color, either all red or all blue. Thus, saying $R(k,k)>n$ means that there exists at least one red-blue edge-coloring of $K_n$ with no monochromatic $K_k$ .

Erdős’s theorem gives a clean condition for such a coloring to exist.

Theorem: If $\binom{n}{k}2^{1-\binom{k}{2}}<1$ , then $R(k,k)>n$ .

The proof begins by coloring every edge of $K_n$ independently and uniformly at random, choosing red with probability $1/2$ and blue with probability $1/2$ . Now fix a particular set $S$ of $k$ vertices. The complete graph on these vertices contains $\binom{k}{2}$ edges. Let $A_S$ be the event that this set $S$ forms a monochromatic $K_k$ . This can happen in exactly two ways: either every edge inside $S$ is red, or every edge inside $S$ is blue.

The probability that all $\binom{k}{2}$ edges are red is $\left(\frac12\right)^{\binom{k}{2}}$ . The probability that all of them are blue is the same: $\left(\frac12\right)^{\binom{k}{2}}$ . Since these two possibilities are disjoint, we get $\mathbb P(A_S)=2\left(\frac12\right)^{\binom{k}{2}}=2^{1-\binom{k}{2}}$ .

There are $\binom{n}{k}$ possible choices for the set $S$ . We now use the union bound. The probability that there exists at least one monochromatic $K_k$ is at most the sum of the probabilities of all the bad events $A_S$ . Therefore,

$\displaystyle \mathbb P(\text{there exists a monochromatic }K_k)\leq \sum_{S\in \binom{[n]}{k}}\mathbb P(A_S)$ .

Since each $A_S$ has probability $2^{1-\binom{k}{2}}$ , this becomes

$\displaystyle \mathbb P(\text{there exists a monochromatic }K_k)\leq \binom{n}{k}2^{1-\binom{k}{2}}$ .

Thus, if $\binom{n}{k}2^{1-\binom{k}{2}}<1$ , then the probability that a random coloring contains a monochromatic $K_k$ is less than $1$ . Hence the probability that it contains no monochromatic $K_k$ is positive. This means at least one good coloring exists, and therefore $R(k,k)>n$ .

This is the probabilistic method in its purest form. We do not explicitly describe the good coloring. We prove that it must exist because a random coloring has a positive chance of being good.

To understand the numerical strength of the result, we now estimate the largest possible $n$ satisfying the inequality. We use the standard estimate

$\binom{n}{k}\leq \frac{n^k}{k!}$ . By Stirling’s formula, $k!\sim \sqrt{2\pi k}\left(\frac{k}{e}\right)^k$ . Ignoring lower-order factors, this gives $k!\approx \left(\frac{k}{e}\right)^k$ , so $\binom{n}{k}\approx \frac{n^k}{(k/e)^k}=\left(\frac{en}{k}\right)^k$ . The condition $\binom{n}{k}2^{1-\binom{k}{2}}<1$ is therefore roughly $\left(\frac{en}{k}\right)^k2^{1-\binom{k}{2}}<1$ .

Since $\binom{k}{2}=\frac{k(k-1)}2$ , we get $\left(\frac{en}{k}\right)^k<2^{\binom{k}{2}-1}=2^{\frac{k(k-1)}2-1}$ . Taking $k$ -th roots gives $\frac{en}{k}<2^{\frac{k-1}{2}-\frac1k}$ , and hence $n<\frac{k}{e}2^{\frac{k-1}{2}-\frac1k}$ . Now $2^{\frac{k-1}{2}}=\frac{2^{k/2}}{\sqrt2}$ , so asymptotically this gives

$\displaystyle R(k,k)>\left(\frac{1}{e\sqrt2}+o(1)\right)k2^{k/2}$ .

This was already a remarkable result. It showed that Ramsey numbers grow exponentially and that random colorings provide strong lower bounds.

Erdős’s original paper can also be interpreted in terms of counting. There are $2^{\binom{n}{2}}$ total red-blue colorings of $K_n$ . Fix a set $S$ of $k$ vertices. The number of colorings in which $S$ is monochromatic is $2\cdot 2^{\binom{n}{2}-\binom{k}{2}}$ . The factor $2$ comes from choosing whether the clique is all red or all blue. The remaining edges outside that clique can be colored freely. Since there are $\binom{n}{k}$ possible sets $S$ , the number of bad colorings is at most $\binom{n}{k}\cdot 2\cdot 2^{\binom{n}{2}-\binom{k}{2}}$ . This equals $\binom{n}{k}2^{1-\binom{k}{2}}2^{\binom{n}{2}}$ . If $\binom{n}{k}2^{1-\binom{k}{2}}<1$ , then the number of bad colorings is strictly smaller than the total number of colorings. Hence at least one coloring is not bad. That coloring avoids monochromatic $K_k$ .

Alteration Method

A later refinement is the alteration method. Instead of requiring the random coloring to be perfect immediately, we allow it to have some bad structures and then delete vertices to destroy them. Randomly color $K_n$ as before, and let $X$ be the number of monochromatic copies of $K_k$ . For each $k$ -vertex set $S$ , define an indicator variable

$\displaystyle X_S=\begin{cases}1,&\text{if }S\text{ spans a monochromatic }K_k,\\ 0,&\text{otherwise.}\end{cases}$

Then we have

$\displaystyle X=\sum_{S\in \binom{[n]}{k}}X_S$ .

By linearity of expectation,

$\displaystyle \mathbb E[X]=\sum_{S\in \binom{[n]}{k}}\mathbb E[X_S]$ .

Since $X_S$ is an indicator random variable,

$\displaystyle \mathbb E[X_S]=\mathbb P(X_S=1)=2^{1-\binom{k}{2}}$ .

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

Now delete one vertex from every monochromatic $K_k$ . If there are $X$ monochromatic cliques, we delete at most $X$ vertices. The remaining graph has no monochromatic $K_k$ , and it has at least $n-X$ vertices. Taking expectations gives $\mathbb E[n-X]=n-\mathbb E[X]=n-\binom{n}{k}2^{1-\binom{k}{2}}$ .

Thus there exists some coloring and deletion process leaving at least $n-\binom{n}{k}2^{1-\binom{k}{2}}$ vertices with no monochromatic $K_k$ . Hence

$\displaystyle R(k,k)>n-\binom{n}{k}2^{1-\binom{k}{2}}$ .

Optimizing this bound gives a better constant. Approximate

$\displaystyle \binom{n}{k}2^{1-\binom{k}{2}}\approx \frac{n^k}{k!}2^{1-\binom{k}{2}}$ .

Let $C=\frac{2^{1-\binom{k}{2}}}{k!}$ . Then the number of remaining vertices is approximately $f(n)=n-Cn^k$ .

To maximize this, differentiate: $f'(n)=1-kCn^{k-1}$ . Setting $f'(n)=0$ gives $1=kCn^{k-1}$ , so $n^{k-1}=\frac1{kC}$ . Since $C=\frac{2^{1-\binom{k}{2}}}{k!}$ , we obtain $n^{k-1}=\frac{k!}{k}2^{\binom{k}{2}-1}=(k-1)!2^{\binom{k}{2}-1}$ . Using Stirling’s formula again, this gives approximately $n\approx \frac{k}{e}2^{k/2}$ . At the maximizing value, the equation $1=kCn^{k-1}$ implies $Cn^k=\frac{n}{k}$ . Therefore, $f(n)=n-Cn^k=n-\frac{n}{k}=n\left(1-\frac1k\right)$ . Since $1-\frac1k\to 1$ , the alteration method gives

$\displaystyle R(k,k)>\left(\frac1e+o(1)\right)k2^{k/2}$ .

This improves the original union-bound constant by a factor of $\sqrt2$ .

Lovász Local Lemma

An even stronger improvement comes from the Lovász Local Lemma. The union bound works when the total probability of all bad events is less than $1$ , but this can be wasteful because it ignores the fact that many bad events are independent. In the Ramsey setting, two bad events only depend on each other if the corresponding $k$ -vertex sets share an edge. If two vertex sets share fewer than two vertices, then their edge sets are disjoint, and the corresponding events are independent.

The symmetric Lovász Local Lemma says that if each bad event has probability at most $p$ , and each bad event depends on at most $d$ other bad events, then it is enough to have $ep(d+1)\leq 1$ to guarantee that with positive probability none of the bad events occur.

In the Ramsey application, the bad event $E_S$ is again the event that a fixed $k$ -vertex set $S$ spans a monochromatic clique. We already computed

$\displaystyle p=\mathbb P(E_S)=2^{1-\binom{k}{2}}$ .

Now we estimate $d$ . Fix $S$ . Another $k$ -vertex set $T$ can depend on $S$ only if $|S\cap T|\geq 2$ .

We can overcount the number of such $T$ by first choosing two vertices from $S$ and then choosing the remaining $k-2$ vertices from the full set of $n$ vertices. This gives $d\leq \binom{k}{2}\binom{n}{k-2}$ .

Therefore, the local lemma applies if $e\left(\binom{k}{2}\binom{n}{k-2}+1\right)2^{1-\binom{k}{2}}<1$ . Equivalently, $\left(\binom{k}{2}\binom{n}{k-2}+1\right)2^{1-\binom{k}{2}}<\frac1e$ .

When this holds, there exists a red-blue edge-coloring of $K_n$ with no monochromatic $K_k$ . Hence $R(k,k)>n$ .

We now optimize this condition. Ignoring the harmless $+1$ , the main inequality is approximately $e\binom{k}{2}\binom{n}{k-2}2^{1-\binom{k}{2}}<1$ . Use $\binom{k}{2}\approx \frac{k^2}{2}$ and $\binom{n}{k-2}\approx \frac{n^{k-2}}{(k-2)!}$ . Then the inequality becomes

$\displaystyle e\cdot \frac{k^2}{2}\cdot \frac{n^{k-2}}{(k-2)!}\cdot 2^{1-\binom{k}{2}}<1$ .

Because $\frac{k^2}{2}\cdot 2=k^2$ , this is approximately

$\displaystyle e k^2\frac{n^{k-2}}{(k-2)!}2^{-\binom{k}{2}}<1$ .

Thus we need $n^{k-2}<\frac{(k-2)!}{ek^2}2^{\binom{k}{2}}$ .

Using Stirling’s formula, $(k-2)!\sim \sqrt{2\pi(k-2)}\left(\frac{k-2}{e}\right)^{k-2}$ . Ignoring subexponential factors, this behaves like $\left(\frac{k}{e}\right)^{k-2}$ . Therefore, $n^{k-2}\lesssim \left(\frac{k}{e}\right)^{k-2}2^{\frac{k(k-1)}2}$ . Taking $(k-2)$ -nd roots gives

$\displaystyle n\lesssim \frac{k}{e}2^{\frac{k(k-1)}{2(k-2)}}$ .

Now simplify the exponent: $\frac{k(k-1)}{2(k-2)}=\frac{k}{2}\cdot \frac{k-1}{k-2}$ .

Since $\frac{k-1}{k-2}=1+\frac1{k-2}$ , we get $\frac{k(k-1)}{2(k-2)}=\frac{k}{2}+\frac{k}{2(k-2)}$ . As $k\to\infty$ , $\frac{k}{2(k-2)}\to \frac12$ . Hence $2^{\frac{k(k-1)}{2(k-2)}}=2^{k/2+1/2+o(1)}=\sqrt2,2^{k/2}(1+o(1))$ .

Therefore the Lovász Local Lemma gives

$\displaystyle R(k,k)>\left(\frac{\sqrt2}{e}+o(1)\right)k2^{k/2}$ .

This is the best known lower bound of this general form. It improves the alteration bound by another factor of $\sqrt2$ , and it improves the original union-bound argument by a factor of $2$ .

Putting the three bounds side by side, we have the union-bound lower bound

$\displaystyle R(k,k)>\left(\frac{1}{e\sqrt2}+o(1)\right)k2^{k/2}$ ,

the alteration-method lower bound

$\displaystyle R(k,k)>\left(\frac1e+o(1)\right)k2^{k/2}$ ,

and the Lovász Local Lemma lower bound

$\displaystyle R(k,k)>\left(\frac{\sqrt2}{e}+o(1)\right)k2^{k/2}$ .

These results show the power of probabilistic reasoning. The first proof shows that a random coloring is likely enough to avoid all bad events when the union bound is strong. The alteration method shows that even if the random object is imperfect, we may repair it by deleting bad parts. The Lovász Local Lemma shows that when bad events have limited dependence, we can do better than the union bound.

The remarkable point is that none of these arguments explicitly constructs the Ramsey coloring. They prove existence indirectly. This is both the beauty and the limitation of the probabilistic method. It tells us that good colorings exist, but it does not necessarily tell us how to find them efficiently.

Constructive Ramsey lower bounds remain difficult. Although random colorings show that many good colorings exist, certifying that a particular coloring avoids monochromatic $K_k$ requires checking many vertex subsets. There are $\binom{n}{k}$ such subsets, which is enormous for large $k$ . Good objects may be abundant, but recognizing one efficiently is still hard.

Upper Bounds:

The upper-bound side comes from the classical Erdős-Szekeres recurrence

$\displaystyle R(a,b)\leq R(a-1,b)+R(a,b-1)$ .

Here is the idea. Choose a vertex $v$ . The remaining vertices split into two sets: those joined to $v$ by red edges and those joined to $v$ by blue edges. If the red-neighbor set has size at least $R(a-1,b)$ , then it contains either a red $K_{a-1}$ , which together with $v$ gives a red $K_a$ , or a blue $K_b$ . The blue-neighbor case is symmetric.

Using the boundary values $\displaystyle R(1,b)=R(a,1)=1$ , this recurrence gives

$\displaystyle R(k+1,\ell+1)\leq \binom{k+\ell}{k}$ .

In particular, for diagonal Ramsey numbers this implies an upper bound of roughly

$\displaystyle R(k,k)\leq (4+o(1))^k$ .

The known lower bounds are still exponentially smaller, of order roughly $k2^{k/2}$ .

Thus, despite major progress, there remains a large exponential gap between the best known lower and upper bounds for diagonal Ramsey numbers. Erdős’s probabilistic method opened the door to this field by showing that randomness can prove the existence of highly structured objects that are extremely difficult to construct explicitly.

Share this:

Related

Leave a comment Cancel reply