# Finite Playground

## Hindman’s Theorem

While reading the posts on ultrafilters by Terry Tao [1,2], I find the following result interesting:

Hindman’s theorem (a special case).  Suppose we color the natural numbers using k colors.  Then there exists a color c and an infinite set S, all colored with c, such that every finite sum of over S has color c as well.

Also, this theorem is claimed to be rather unpleasant to prove if we insist on not using ultrafilters.

## 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$.  整理不等式便得出我們的結果.