拉姆齐数一个下界的概率证明

拉姆齐定理表明在二染色中对任意整数 $r$ 一定存在 $n$,使得完全图 $K_n$ 必然包含的同色子完全图$K_s$。$R(s):=R(s,s)$. 我们已经知道 $R(1)=1$, $R(2)=2$, $R(3)=6$, 以及 $R(4)=18$. 然后寻找确切的拉姆齐数十分困难, 事实上, $R(5)$ 及其以上的确切值仍然没有确定. 因此, 自然的想法就是不断缩小上下界. P. Erdös

- 阅读全文 -

方程的染色问题

本文翻译节选自我的一个笔记,为了偷懒,一些定义和证明就保持原样了。染色问题最著名的理论是拉姆齐理论,它描述的是对有限整数集合或者所有自然数的任意染色下局部拥有的单色性。这一定理可以推广到可数甚至与一些大基数(large cardinals)。关于无限的拉姆齐理论可以参考这个 Notes。至于满足单色性的局部性质,拉姆齐定理并没有给出这些性质的具体形式。然而, Van der Waerden 定理和

- 阅读全文 -