A lower bound to Ramsey numbers and an application

Ramsey’s Theorem.  $R(p_1,\ldots,p_k;r)$ is finite.

$R(p_1,\ldots,p_k;r) \le R(p_1',\ldots,p_k';r-1)+1$, where $p_i' = R(p_1,\ldots,p_{i}-1,\ldots,p_k;r)$.

Theorem. $R(p,p) = \Omega(p 2^{p/2})$.
Proof.  每個特定的$p$-clique 或$p$-independent set 出現的機會都是$2^{-{p \choose 2}}$; 因此若$2{n \choose p} 2^{{n \choose 2}-{p\choose 2}} < 2^{n \choose 2}$的話就表示某個大小為$n$的圖同時沒有大小為$p$的 cliques 或 independent sets, 因此$R(p,p) > n$.  整理不等式便得出我們的結果.

Author: hcsoso

Ph.D. student in the Department of Computer Science, University of Illinois at Urbana-Champaign.