11.4: Applying Probability to Ramsey Theory

The following theorem, due to P. Erdős, is a true classic, and is presented here in a manner that is faithful to how it was first published. As we shall see later, it was subsequently recast—but that's getting the cart ahead of the horse.

Theorem 11.4

If \(n\) is a positive integer. Then

\(R(n,n) \geq \dfrac{n}{e \sqrt{2}} 2^{\frac{1}{2}n}\)

Proof

Let \(t\) be an integer with \(t>n\) and consider the set \(\mathcal{F}\) of all labeled graphs with vertex set \(\{1,2,…,t\}\). Clearly, there are \(2^{C(t,2)}\) graphs in this family. Let \(\mathcal{F_1}\) denote the subfamily consisting of those graphs which contain a complete subgraph of size \(n\). It is easy to see that

\(|\mathcal{F_1}| \leq \dbinom{t}{n} 2^{n(t-n)}2^{C(t-n,2)}\).

Similarly, let \(\mathcal{F_2}\) denote the subfamily consisting of those graphs which contain an independent set of size \(n\). It follows that

\(|\mathcal{F_2}| \leq \dbinom{t}{n} 2^{n(t-n)}2^{C(t-n,2)}\).

We want to take the integer \(t\) as large as we can while still guaranteeing that \(|\mathcal{F_1}|+|\mathcal{F_2}| \leq |\mathcal{F}|\). This will imply that there is a graph \(G\) in \(\mathcal{F}\) which does not contain a complete subgraph of size \(n\) or an independent set of size \(n\). So consider the following inequality:

\[2 \dbinom{t}{n} 2^{n(t-n)}2^{C(t-n,2)} < 2^{C(t,2)} \label{11.4.1} \]

Now we ask how large can t be without violating inequality(\(\ref{11.4.1}\))? To answer this, we use the trivial inequality \( \binom{t}{n} \leq t^n/n!\) and the use the Stirling approximation for \(n!\). After some algebra and taking the \(n^{th}\) root of both sides, we see that we need only guarantee that

\(t \leq \dfrac{n}{e \sqrt{n}} 2^{\frac{1}{2}n}\)

Now let's take a second look at the proof of Theorem 11.4. We consider a probability space \((S,P)\) where the outcomes are graphs with vertex set \(\{1,2,…,t\}\). For each \(i\) and \(j\) with \(1 \leq i<j \leq t\), edge \(ij\) is present in the graph with probability 1/2. Furthermore, the events for distinct pairs are independent.

Let \(X_1\) denote the random variable which counts the number of \(n\)-element subsets of \(\{1,2,…,t\}\) for which all \(\binom{n}{2}\) pairs are edges in the graph. Similarly, \(X_2\) is the random variable which counts the number of \(n\)-element independent subsets of \(\{1,2,…,t\}\). Then set \(X=X_1+X_2\).

By linearity of expectation, \(E(X)=E(X_1)+E(X_2)\) while

\(E(X_1) = E(X_2) = \dbinom{t}{n} \dfrac{1}{2^{C(n,2)}}\).

If \(E(X)<1\), then there must exist a graph with vertex set \(\{1,2,…,t\}\) without a \(K_n\) or an \(I_n\). And the question of how large \(t\) can be while maintaining \(E(X)<1\) leads to exactly the same calculation we had before.

After more than fifty years and the efforts of many very bright researchers, only marginal improvements have been made on the bounds on \(R(n,n)\) from Theorem 11.2 and Theorem 11.4. In particular, no one can settle whether there is some constant \(c<2\) and an integer \(n_0\) so that \(R(n,n)<2^{cn}\) when \(n>n_0\). Similarly, no one has been able to answer whether there is some constant \(d>1/2\) and an integer \(n_1\) so that \(R(n,n)>2^{dn}\) when \(n>n_1\). We would certainly give you an \(A\) for this course if you managed to do either.

Discussion 11.5.

Carlos said that he had been trying to prove a good lower bound on \(R(n,n)\) using only constructive methods, i.e., no random techniques allowed. But he was having problems. Anything he tried seemed only to show that \(R(n,n) \geq n^c\) where \(c\) is a constant. That seems so weak compared to the exponential bound which the probabilistic method gives easily. Usually Alice was not very sympathetic to the complaints of others and certainly not from Carlos, who seemed always to be out front. But this time, Alice said to Carlos and in a manner that all could hear “Maybe you shouldn't be so hard on yourself. I read an article on the web that nobody has been able to show that there is a constant \(c>1\) and an integer \(n_0\) so that \(R(n,n)>c^n\) when \(n>n_0\), provided that only constructive methods are allowed. And maybe, just maybe, saying that you are unable to do something that lots of other famous people seem also unable to do is not so bad.” Bob saw a new side of Alice and this too wasn't all bad.