Applying the Local Lemma

The list of applications of the Local Lemma has been growing steadily, as has the interest in how the lemma can be applied algorithmically, , in a constructive setting. But here we present one of the early applications to Ramsey theoryestimating the Ramsey number \((R,3,n)\). Recall that we have the basic inequality \(R(3,n)\le \binom{n+1}{3}\) from , 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\). So we would want no triangles, and that would say we need \(t^3p^3=1\), , \(p=1/t\). Then we would want no independent sets of size \(n\), which would require \(n^te^{-pn^2}=1\), , \(t\ln n=pn^2\), so we can't even make \(t\) larger than \(n\). 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 . Along these lines, we would set \(t^3p^3=t\), , \(p=t^{-2/3}\). And the calculation now yields the lower bound \(R(3,n)\ge n^{6/5}/\ln^{-3/5} n\), 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\), 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\). For each \(3\)-element subset \(S\), we have the event \(E_S\) which is true when \(S\) forms a triangle. For each \(n\)-element set \(T\), 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\), respectively. Note that the probability of \(S\) is \(p^3\) for each \(3\)-element set \(S\), while the probability of \(T\) is \(q=(1-p)^{C(n,2)}\sim e^{-pn^2/2}\) for each \(n\)-element set \(T\).

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

Condensed — the full section is in Keller & Trotter, Applied Combinatorics.