An Exponential Lower Bound for R(k,k)

The Random Coloring Idea

A lower-bound construction for a Ramsey number must produce a coloring that avoids the monochromatic subgraphs in question. Rather than specify every edge color, we can choose each edge color independently at random and count the expected number of monochromatic cliques. If that expected count is less than one, at least one coloring has no monochromatic clique at all. The key is to choose the number of vertices so that the number of candidate cliques grows more slowly than the probability that any one is monochromatic decreases.

In this tutorial, each edge of \(K_n\) is colored red or blue, with the two choices equally likely, and the choices for distinct edges are independent. There are \(2^{\binom{n}{2}}\) such colorings, all equally likely. We use this finite probability space only to show that at least one suitable coloring exists.

Counting Monochromatic Cliques in Expectation

Fix a set \(S\) of \(k\) vertices. Its induced complete graph has \(q=\binom{k}{2}=k(k-1)/2\) edges. For all these edges to be red has probability \(2^{-q}\); for all of them to be blue has the same probability. Since \(k\ge2\), these two events are disjoint. Thus the probability that this particular \(K_k\) is monochromatic is \(2^{1-q}\).

For each \(k\)-vertex set \(S\), let \(I_S\) equal \(1\) if the clique on \(S\) is monochromatic and \(0\) otherwise. Let \(X\) be the total number of monochromatic \(K_k\) subgraphs. Then \(X=\sum_S I_S\), where the sum is over all \(k\)-vertex subsets of \(V(K_n)\).

Proof. For each set \(S\), \(I_S\) is \(1\) with probability \(2^{1-\binom{k}{2}}\) and \(0\) otherwise, so its expectation is that probability. The expectation of a finite sum is the sum of the expectations; this follows by writing each expectation as a sum over the finite set of colorings and distributing the finite sums. There are \(\binom{n}{k}\) possible sets \(S\). Therefore \(\mathbb{E}[X]=\binom{n}{k}2^{1-\binom{k}{2}}\). This argument does not require different clique indicators to be independent, even when their vertex sets overlap. \(\square\)

The decisive threshold is strict. If \(\mathbb{E}[X]<1\), some coloring must have \(X=0\): otherwise every coloring would have the nonnegative integer \(X\ge1\), forcing its average to be at least \(1\). A coloring with \(X=0\) contains no monochromatic \(K_k\), so it gives a lower bound on \(R(k,k)\).

Bounding the Expected Count

We now estimate the binomial coefficient to make the expected-count formula useful for large \(k\). For integers \(n\ge k\ge1\), \(\binom{n}{k}\le n^k/k!\). We also use \(k!\ge(k/e)^k\). To justify the latter estimate, take natural logarithms. Since \(\ln x\) is increasing, for each integer \(j\) with \(1\le j\le k-1\), \(\ln x\le\ln(j+1)\) on \([j,j+1]\). Adding the resulting integral inequalities gives $$ \ln(k!)=\sum_{j=1}^k\ln j\ \ge\ \int_1^k\ln x\,dx =k\ln k-k+1\ \ge\ k\ln k-k. $$ Exponentiating gives \(k!\ge(k/e)^k\), including \(k=1\). Consequently \(\binom{n}{k}\le(en/k)^k\).

Proof. Set \(c=1/(4e)\) and \(n=\lfloor c k2^{k/2}\rfloor\). For all sufficiently large \(k\), \(n\ge k\), because \(c2^{k/2}\) grows without bound. Apply the counting formula and the binomial estimate: $$ \mathbb{E}[X] =\binom{n}{k}2^{1-k(k-1)/2} \le 2\left(\frac{en}{k}\right)^k2^{-k(k-1)/2}. $$ Since \(n\le c k2^{k/2}\), we have \(en/k\le ec\,2^{k/2}\). Substituting this bound and combining the powers of \(2\) gives $$ \mathbb{E}[X] \le 2(ec)^k2^{k^2/2}2^{-k(k-1)/2} =2(ec\sqrt{2})^k =2\left(\frac{1}{2\sqrt{2}}\right)^k. $$ For \(k\ge2\), this last quantity is less than \(1\): at \(k=2\) it is \(2(1/8)=1/4\), and each increase in \(k\) multiplies it by \(1/(2\sqrt{2})<1\). Thus, for sufficiently large \(k\), a coloring of \(K_n\) exists with no monochromatic \(K_k\). By the definition of \(R(k,k)\), this implies \(R(k,k)>n\). Since \(R(k,k)\) is an integer and \(n=\lfloor c k2^{k/2}\rfloor\), \(R(k,k)>n\) implies \(R(k,k)>c k2^{k/2}\), as claimed. \(\square\)

Interpreting the Bound and Avoiding Pitfalls

The estimate comes from balancing two quantities: there are \(\binom{n}{k}\) candidate cliques, while any fixed one is monochromatic with probability \(2^{1-\binom{k}{2}}\). The factor \(2^{-\binom{k}{2}}\) decreases rapidly as \(k\) grows. Taking \(n\) proportional to \(k2^{k/2}\) keeps the product small enough to force a coloring with no monochromatic \(K_k\). The theorem establishes an exponential lower bound; it does not assert that its constant is best possible.

Common mistake: losing the factor of two. For a fixed \(K_4\), there are 6 edges. The probability that all are red is \(2^{-6}=1/64\), but being monochromatic also allows all 6 to be blue. These two events are disjoint, so the correct probability is \(2/64=1/32\), not \(1/64\). For example, in \(K_6\), using the incorrect probability would give \(15/64\) instead of the correct expectation \(15/32\).

Common mistake: replacing “less than one” by “at most one.” The argument guarantees a zero count only when the expectation is strictly below \(1\). If an integer-valued nonnegative random variable is always at least \(1\), its expectation can equal \(1\); equality alone does not force a zero value. For instance, the calculation for \(K_4\) with \(k=3\) gives \(\binom{4}{3}2^{1-3}=4/4=1\). That equality does not justify the first-moment conclusion. The strict inequality in the theorem is therefore essential to this argument.