Lesson 4

It is not immediately obvious why the definition of \(R(k,l)\) is even valid: what if for some parameters \(l\) and \(k\), for any sufficiently large \(n\), there exists a graph with \(n\) vertices that contains neither a clique of size \(k\) nor an independent set of size \(l\)? Below, we will prove that this definition is indeed valid. Before stating the theorem, we note two simple facts:

• For any \(k,l \in \mathbb{Z}_{\ge 1}\), it holds that \(R(k,1)=R(1,l)=1\): in any graph with at least one vertex, there exists both a clique of size one and an independent set of size one.


• If for some \(n\) the required property holds, then it certainly holds for all larger \(n\). For example, we know that \(R(3,3)=6\): in any group of six people, there exist three who know each other or three who do not. But then this property certainly holds for, say, twenty-five people as well: we can simply take any six of them and use the previous result.

Problem. Let \(k \ge 2\). Find \(R(k,2)\).