图论

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

拉姆齐定理表明在二染色中对任意整数 rr 一定存在 nn,使得完全图 KnK_n 必然包含的同色子完全图KsK_s

R(s):=R(s,s)R(s):=R(s,s). 我们已经知道 R(1)=1R(1)=1, R(2)=2R(2)=2, R(3)=6R(3)=6, 以及 R(4)=18R(4)=18. 然后寻找确切的拉姆齐数十分困难, 事实上, R(5)R(5) 及其以上的确切值仍然没有确定. 因此, 自然的想法就是不断缩小上下界. P. Erdös 在其1947年的文章中开创性的利用概率方法给出第一个下界.