# Proof of Ramsey's theorem: the number of cliques or anti cliques in a graph

Ramsey's theorem states that every graph with $n$ nodes contains either a clique or an independent set with at least $\frac{1}{2}\log_2 n$ nodes.

I tried to look it up at a few places (including Sipser) but I could not make out a lot of sense from the proofs. I would appreciate it if someone can give me a proof (or clear intuition) on this.

• Does anyone know how to BUILD the proof? i mean surely he came up with some idea that led to this statement, so can anyone tell me how to construct it (and not prove it with induction?) i am guessing it should be something simple.. something elegant! – Subhayan Sep 12 '13 at 7:02

Let $R(s,t)$ be the least integer $k$ such that every graph on $k$ or more vertices contains either a $s$-clique or independent set of size $t.$

It turns out that this number is well defined (called Ramsey number) and the statement in your question merely amount to saying that $$R(t,t) \leq 2^{2t}.$$

A well known upper bound for Ramsey number states $$R(s,t) \leq R(s,t-1)+R(s-1,t) \leq {s+t-2 \choose t-1} \; \; \; (1)$$ if $s = t$ then the above reduces to the central binomial coefficient ${2t-2 \choose t-1}$ which is always smaller than $2^{2t}$

To prove $(1)$ one can use induction on $s+t$. Leaving the induction base $R(1,t), R(s,1)$ as an exercise for you let us suppose the inequality holds for all $s+t < k$ and let $G$ be a graph with $R(s,t-1)+R(s-1,t)$ vertices.

Let $v$ be an arbitrary vertex of $G$ and partition the remaining vertices of the graph into two groups $A,N$ - those adjacent with $v$ and those that are not adjacent with $v.$ Now since $$|A|+|N|+1 = R(s,t-1)+R(s-1,t)$$ we have either $$|N| \geq R(s,t-1) \quad \mbox{ or} \quad |A| \geq R(s-1,t).$$ Now if the first inequality is satisfied then the graph induced by $N$ either contains a $s$-clique or the graph induced by $N \cup \{v\}$ contains an independent set of size $t.$ In particular this implies that in this case $G$ either contains a $s$-clique or independent set of size $t.$ The second case is verified analogously and establishes the first part of the stated bound. For the last part observe that $${s+t-3 \choose s-1} + {s+t-3 \choose s-2} = {s+t-2 \choose s-1}.$$

• Not sure it is. Since $|A| < 2^{2(t-1)}$ it follows that $|A|+1 \leq 2^{2(t-1)}$ – Jernej Aug 26 '13 at 9:11
• You're right the step is wrong! Somehow I was sure it was possible to prove the result only making use of the diagonal Ramsey numbers but I don't see how to fix it in that way.. – Jernej Aug 26 '13 at 15:31
• @AndrásSalamon Please flag these comments as obsolete once you agree everything is fine now. – Raphael Aug 26 '13 at 17:59