Lesson 5

Theorem. For any \(k,l \in \mathbb{Z}_{\ge 2}\), the following holds: \[R(k,l) \le R(k-1,l)+R(k,l-1) \ .\]

Proof. We will prove by induction on \(k\) and \(l\). If \(k=2\), then \[l=R(2,l)=R(1, l)+R(2,l-1)=1+(l-1).\] The case \(l=2\) is handled similarly.

Now suppose \(k,l>2\). Consider a graph \(G(V,E)\) with sufficiently many vertices: \(|V| \ge R(k-1,l)+R(k,l-1)\). Our goal is to show that \(G\) necessarily contains a \(k\)-clique or an \(l\)-independent set.

Take an arbitrary vertex \(v \in V\) and denote by \(A \subseteq V\) its neighbors, and by \(B=V \setminus A \setminus \{v\}\) all other vertices. We know that \[|V|=1+|A|+|B| \ge R(k-1,l)+R(k,l-1) \ .\] Thus, it cannot be that both \(|A| < R(k-1,l)\) and \(|B| < R(k,l-1)\). Consider two cases:

1. \(|A| \ge R(k-1,l)\). Then \(G[A]\) definitely contains a \((k-1)\)-clique or an \(l\)-independent set. The latter immediately satisfies our requirement. If \(G[A]\) contains a \((k-1)\)-clique, then adding vertex \(v\) to it forms a \(k\)-clique in \(G\) (recall that \(v\) is connected to all vertices in \(A\)).
2. \(|B| \ge R(k,l-1)\). If \(G[B]\) contains a \(k\)-clique, then we are done. If \(G[B]\) contains an \((l-1)\)-independent set, then adding vertex \(v\) to it forms an \(l\)-independent set in \(G\).