Applied Combinatorics

The list of applications of the Local Lemma has been growing steadily, as has the interest in how the lemma can be applied algorithmically, i.e., in a constructive setting. But here we present one of the early applications to Ramsey theory—estimating the Ramsey number \((R,3,n)\text{.}\) Recall that we have the basic inequality \(R(3,n)\le \binom{n+1}{3}\) from Theorem 11.2, and it is natural to turn to the probabilistic method to look for good lower bounds. But a few minutes thought shows that there are challenges to this approach.

First, let’s try a direct computation. Suppose we try a random graph on \(t\) vertices with edge probability \(p\text{.}\) So we would want no triangles, and that would say we need \(t^3p^3=1\text{,}\) i.e., \(p=1/t\text{.}\) Then we would want no independent sets of size \(n\text{,}\) which would require \(n^te^{-pn^2}=1\text{,}\) i.e., \(t\ln n=pn^2\text{,}\) so we can’t even make \(t\) larger than \(n\text{.}\) That’s not helpful.

We can do a bit better by allowing some triangles and then removing one point from each, as was done in the proof for Theorem 11.7. Along these lines, we would set \(t^3p^3=t\text{,}\) i.e., \(p=t^{-2/3}\text{.}\) And the calculation now yields the lower bound \(R(3,n)\ge n^{6/5}/\ln^{-3/5} n\text{,}\) so even the exponent of \(n\) is different from the upper bound.

So which one is right, or is the answer somewhere in between? In a classic 1961 paper, Erdős used a very clever application of the probabilistic method to show the existence of a graph from which a good lower bound could be extracted. His technique yielded the lower bound \(R(3,n)\ge n^2/\ln^2 n\text{,}\) so the two on the exponent of \(n\) is correct.

Here we will use the Lovász Local Lemma to obtain this same lower bound in a much more direct manner. We consider a random graph on \(t\) vertices with edge probability \(p\text{.}\) For each \(3\)-element subset \(S\text{,}\) we have the event \(E_S\) which is true when \(S\) forms a triangle. For each \(n\)-element set \(T\text{,}\) we have the event \(E_T\) which is true when \(T\) is an independent set. In the discussion to follow, we abuse notation slightly and refer to events \(E_S\) and \(E_T\) as just \(S\) and \(T\text{,}\) respectively. Note that the probability of \(S\) is \(p^3\) for each \(3\)-element set \(S\text{,}\) while the probability of \(T\) is \(q=(1-p)^{C(n,2)}\sim e^{-pn^2/2}\) for each \(n\)-element set \(T\text{.}\)

When we apply the Local Lemma, we will set \(x=x(S)\) to be \(e^2p^3\text{,}\) for each \(3\)-element set \(S\text{.}\) And we will set \(y=Y(T)=q^{1/2}\sim e^{-pn^2/4}\text{.}\) It will be clear in a moment where we got those values.

Similarly, we want to keep the term \((1-x)^{t}\) relatively large, so we keep \(t\le 1/x\text{,}\) i.e., \(t\le 1/p^3\text{.}\) On the other hand, we want only to keep the term \((1-x)^{tn^2}\sim e^{-xtn^2}\) at least as large as \(y\text{.}\) This is equivalent to keeping \(p\le xt\text{,}\) and since \(x\sim p^3\text{,}\) this can be rewritten as \(p^{-1}\le t^{1/2}\text{.}\)

Now we have our marching orders. We just set \(\ln t=pn\) and \(p^{-1}=t^{1/2}\text{.}\) After substituting, we get \(t= n^2/\ln^2t\) and since \(\ln t=\ln n\) (at least within the kind of approximations we are using), we get the desired result \(t=n^2/\ln^2n\text{.}\)