7
$\begingroup$

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.

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – Subhayan Sep 12 '13 at 7:02
6
$\begingroup$

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}.$$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Not sure it is. Since $|A| < 2^{2(t-1)}$ it follows that $|A|+1 \leq 2^{2(t-1)}$ $\endgroup$ – Jernej Aug 26 '13 at 9:11
  • $\begingroup$ 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.. $\endgroup$ – Jernej Aug 26 '13 at 15:31
  • $\begingroup$ @AndrásSalamon Please flag these comments as obsolete once you agree everything is fine now. $\endgroup$ – Raphael♦ Aug 26 '13 at 17:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.