I've been presented with the following problem:
Prove that a graph with $\binom{k+l}{k}$ vertices contains $K_{k+1}$ or $\overline K_{l+1}$
It seems to me that a good way to prove this would be using Ramsey's Theorem. But I don't know where to start. Maybe showing that $\binom{k+l}{k}$ is an upper bound for Ramsey numbers? If so what should it bound: $R(k)$ or $R(l)$? And how should I go about proving this bound? I'm stumped.
Lemma. $R(r, s) \leq R(r-1, s) + R(r, s-1)$.
Proof. Let $N = R(r-1, s) + R(r, s-1)$, and let the edges of $K_N$ have a $2$-coloring in, say, red and blue. Fix a vertex $V$ in $K_N$, and partition the other $(N-1)$ vertices of $K_N$ into sets $R$, which contains all vertices with a red edge to $V$, and $B$, which contains all vertices with a blue edge to $V$.
By the pigeonhole principle, either $R$ has at least $R(r-1, s)$ vertices, or $B$ has at least $R(r, s-1)$ vertices. In the former case, $R$ must either contain a red $K_{r-1}$ or a blue $K_s$. If $R$ contains a red $K_{r-1}$, then the graph formed by $K_{r-1}$ and $V$ is a red $K_r$. If $R$ has a blue $K_s$, we are done. Similarly, in the latter case, $B$ contains either a red $K_r$ or a blue $K_{s-1}$. A blue $K_{s-1}$, including $V$, forms a blue $K_s$. Thus, $N$ must contain either a red $K_r$ or blue $K_s$, so $R(r, s) \leq N$.
Now, we will show by induction that $$ R(r, s) \leq \binom{r+s-2}{r-1}. $$
The base case holds, since $R(2, 2) = 2$. Then, by our lemma, $$ R(r, s) \leq R(r - 1, s) + R(r, s - 1) \leq \binom{r + s - 3}{r - 2} + \binom{r + s - 3}{r - 1} = \binom{r + s - 2}{r - 1}, $$ where the last step holds by Pascal's identity.