Erdös theorem which gives a weaker lower bound for R(k,k)

Question

I have proved the theorem of Erdös that gives a lower bound for $R(k,k)$ and it is exponential in k. I have used probabilistic method to find this lower bound: $R(k,k) > (1+o(1))\frac {k}{(e√2)} √(2^k )$.

My question is: How can we construct a family of graphs that show this : $R(k,k) ≥ (k-1)^2$

I know that this is a weaker lower bound, but how to prove it?

I checked this link: Lower bound for the Ramsey number $r(k,k)$ but still I am missing some details to understand the hint that is given in this link.

If someone could help me, I would appreciate it :)

Answer 1

Suppose that $G$ is the union of $k-1$ disjoint $(k-1)$-cliques, so that $\overline{G}$ is the complete $(k-1)$-partite graph $K_{k-1,k-1,\dots,k-1}$.

Another way to say this is that $V(G) = V(\overline{G})$ is partitioned into $k-1$ sets $S_1, S_2, \dots, S_{k-1}$ of size $k-1$. Two vertices are adjacent in $G$ if they're in the same set, and they're adjacent in $\overline{G}$ if they're in different sets.

Now suppose that we pick any $k$ distinct vertices.

1. They cannot all be in the same set, because each set only has size $k-1$, and we are picking $k>k-1$ vertices. So at least two of them are in different sets - and those two vertices are not adjacent in $G$. Therefore $G$ does not have a clique of size $k$.
2. By the pigeonhole principle, since we have $k$ vertices and each of them is in one of the $k-1$ sets $S_1, S_2, \dots, S_{k-1}$, two vertices must be in the same set. Those two vertices are not adjacent in $\overline{G}$. Therefore $\overline{G}$ does not have a clique of size $k$.