If $R(k)$ is the minimum number of vertices that ensures a monochromatic $k$ clique in an arbitrary edge 2 coloring of $K_{R(k)}$ (Complete Graph), I read a proof that establishes an upper bound of $2^{2k}$ on $R(k)$ in a very elegant manner which is as follows –
Consider a vertex $x_1$, given a $2$-coloring of $K_{2^{2k}}$.
A set $A_1$ of at least $2^{2k-1}$ vertices is such that every edge from $x_1$ to $A_1$ is of the same color. Now consider a vertex $x_2$ inside $A_1$. We can find a set of $2^{2k-2}$ vertices $A_2$, contained inside $A_1$ such that every edge from $x_2$ to $A_2$ is of the same color.
Continuing like this, we get $\{x_1, x_2, \cdots ,x_{2k}\}$ and $\{A_1, A_2,\cdots,A_{2k}\}$ such that $A_i$ contains $x_{i+1}, x_{i+2}, \cdots$ and all edges from $x_i$ to $A_i,A_{i+1},A_{i+2},\cdots,A_{2k}$ are of the same color. Therefore color of edge $\{x_i,x_j\}$ only depends on $\min\{i,j\}$.
Therefore, by pigeonhole we can find a set of $k$ vertices among $\{x_1, x_2, \cdots ,x_{2k}\}$ that have same color edges among one another and hence form a monochromatic clique.
How does one extend this argument to get a upper bound of $R(k)<$$ {2k}\choose{k}$?
Best Answer
Let $G$ be a graph with $ \begin{pmatrix}2k\\k\\\end{pmatrix}$ vertices and let us suppose for convenience that the vertices are totally ordered. Let $x_1$ be the first vertex. Then by the pigeonhole principle there is a set of vertices $A_1$ of size at least $ \begin{pmatrix}2k-1\\k\\\end{pmatrix}$ such that every edge from $x_1$ to $A_1$ has the same colour.
This process is continued. So suppose we have a set $A_i$ of $\begin{pmatrix}m\\n\\\end{pmatrix}$ vertices and $x_{i+1}$ is the least vertex of $A_i$. Let $X$ be a colour that has been chosen at least as often as the other colour. Applying the pigeonhole principle, there is a subset $A_{i+1}$ of $A_i$ of size at least $\begin{pmatrix}m-1\\n\\\end{pmatrix}$ such that every edge from $x_{i+1}$ to $A_{i+1}$ has colour $X$ or of size at least $\begin{pmatrix}m-1\\n-1\\\end{pmatrix}$ such that every edge from $x_{i+1}$ to $A_{i+1}$ has the other colour. Continuing this process, we obtain a sequence $x_1, … ,x_l$ of vertices and a sequence $A_1\supset … \supset A_l$ of sets such that $x_i\in A_{i-1}$ for every $i$, every edge from $x_i$ to $A_i$ has the same colour and $| A_l |=1.$
Suppose that in this process red has been chosen $r$ times and blue $b$ times. W.l.g suppose $r\ge b$. Then $$\begin{pmatrix}2k-r-b\\k-b\\\end{pmatrix}=1$$ and so $r=k$. The colour of the edge joining $x_i$ to $x_j$ depends only on min$\{i,j\}$. We can therefore find a subset $H$ of $x_1, … ,x_{2k}$ of size $k$ such that this colour is always the same, so that all edges joining vertices in $H$ have the same colour.