Erdős's Exponential Lower Bound for R(k,k)

From Random Graphs to a Ramsey Lower Bound

The diagonal Ramsey number \(R(k,k)\) is the least number of vertices that forces every simple graph to contain either a clique of size \(k\) or an independent set of size \(k\). A clique is a set whose pairs are all edges; an independent set is a set whose pairs are all nonedges. To prove a lower bound for \(R(k,k)\), it is enough to construct, or prove the existence of, a graph on \(n\) vertices containing neither kind of set. The first-moment method gives such a construction without having to identify its edges explicitly.

We use the random graph \(G(n,p)\): its vertex set is \(\{1,\ldots,n\}\), and each of the \(\binom{n}{2}\) possible edges is included independently with probability \(p\), where \(0\le p\le1\). Thus each outcome is a finite simple graph on this fixed vertex set. For the diagonal problem, taking \(p=1/2\) gives the same probability to every possible edge choice and treats cliques and independent sets symmetrically.

We will bound the expectation of \(X\), the average value of this nonnegative integer over the random graph. If that expectation is below one, at least one outcome must have \(X=0\): if every outcome had \(X\ge1\), their average would be at least one. The useful work is therefore to count the obstructions correctly and choose \(n\) so that their expected total is below one.

Counting the Expected Obstructions

Fix a particular \(k\)-vertex subset \(S\). It is a clique exactly when all \(\binom{k}{2}\) possible edges within \(S\) are present. Independence of the edge choices gives probability \(p^{\binom{k}{2}}\). It is an independent set exactly when all those edges are absent, which has probability \((1-p)^{\binom{k}{2}}\). There are \(\binom{n}{k}\) possible subsets. Adding their indicator variables and using linearity of expectation gives the count below; independence between the different subset indicators is not required.

When \(n<k\), there are no \(k\)-vertex subsets, so \(X=0\) for every outcome and the displayed expectation is zero. For \(n\ge k\) and \(p=1/2\), the two probabilities are equal, and the expression becomes

The factor of two matters: we are counting both types of obstruction. To make the expression small, use the elementary estimate \(\binom{n}{k}\le n^k/k!\). The resulting bound suggests taking \(n\) on the scale of \(2^{(k-1)/2}\), because \(n^k\) then cancels the exponential factor \(2^{-\binom{k}{2}}\), leaving a factorial denominator.

Proof. Suppose instead that every outcome has \(X\ge1\). Then the average value of \(X\), taken over the outcomes with their probabilities, is at least the average value of the constant \(1\), which is \(1\). This contradicts \(\mathbb{E}[X]<1\). Therefore some outcome has \(X=0\). \(\square\)

Erdős's Exponential Lower Bound

Proof. Fix \(k\ge3\) and set \(n=\left\lfloor 2^{(k-1)/2}\right\rfloor\). If \(n<k\), then \(G(n,1/2)\) has no \(k\)-vertex subset at all, so it already has neither obstruction. Suppose \(n\ge k\). The expectation formula and \(\binom{n}{k}\le n^k/k!\) give

The last equality follows because \(\left(2^{(k-1)/2}\right)^k=2^{k(k-1)/2}\). Since \(k\ge3\), \(k!\ge3!=6\), so \(2/k!\le1/3<1\). The lemma therefore supplies an outcome on \(n\) vertices with \(X=0\). This graph has neither a \(k\)-clique nor a \(k\)-vertex independent set.

By definition, \(R(k,k)\) is the least order for which every graph has one of these two sets. A graph on \(n\) vertices without either set shows that this forcing property does not hold at order \(n\). It cannot hold at any smaller order either: if it held at some order \(r\le n\), every \(n\)-vertex graph would contain an induced \(r\)-vertex subgraph, and that subgraph would contain the required set. Hence \(R(k,k)>n\), as claimed. \(\square\)

This is an exponential lower bound: the threshold grows as a constant multiple of \(2^{k/2}\). More explicitly, for \(x=2^{(k-1)/2}\ge1\), \(\lfloor x\rfloor\ge x/2\). Thus the theorem gives a lower bound of exponential order, not merely a polynomial one. The floor is useful because the number of vertices must be an integer; the theorem asserts a strict inequality above that integer.

Worked Parameter Choices

What the Argument Does—and Does Not—Say

The key choice \(p=1/2\) balances the two obstruction types: a fixed \(k\)-set is a clique with probability \(2^{-\binom{k}{2}}\), and it is an independent set with the same probability. The choice of \(n\) then makes the sum of their expected counts less than one. This is an existence proof: the argument guarantees at least one successful graph among the possible outcomes, but it does not specify its edge set.

A common mistake is to count only one obstruction type. For \(k=7,n=8\), the expected number of cliques alone is \(1/262{,}144\). Treating that as the expected total is incorrect: the independent sets contribute another \(1/262{,}144\), so the total is \(1/131{,}072\). The corrected total is still below one, but both terms must be included to justify the conclusion about graphs with neither type of set.

A second pitfall is to interpret an expectation below one as saying that a typical random graph has no obstruction, or that the probability of an obstruction equals the expectation. Neither claim follows. The argument uses only the integer-valued nature of \(X\): if every outcome had at least one obstruction, the expectation could not be below one. That distinction is central to using the first-moment method correctly.