组合

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

拉姆齐定理表明在二染色中对任意整数 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年的文章中开创性的利用概率方法给出第一个下界.

方程的染色问题

本文翻译节选自我的一个笔记,为了偷懒,一些定义和证明就保持原样了。

染色问题最著名的理论是拉姆齐理论,它描述的是对有限整数集合或者所有自然数的任意染色下局部拥有的单色性。这一定理可以推广到可数甚至与一些大基数(large cardinals)。关于无限的拉姆齐理论可以参考这个 Notes。至于满足单色性的局部性质,拉姆齐定理并没有给出这些性质的具体形式。然而, Van der Waerden 定理和 Hales–Jewett 定理等结论给出了一些具体的形式,比如前者是等差数列总有单色解,后者更是前者的推广。另一个有意思的局部性质是“单色方程解”,满足这一特性的方程我们称为“分割正规的”(partition regular)。

完美正方形

完美正方形是把整数边长的正方形分割为若干个不等整数边长的小正方形. 我们接下来讨论的所有分割均是边长为整数的分割. 如果不限制边长不等, 我们很容易可以用小正方形分割正方形. 完美正方形如果其中任何一部分小正方形都无法构成一个矩形或正方形, 则称为简单完美正方形(Simple Perfect Squared Square, SPSS), 否则称为复合完美正方形(Compound Perfect Squared Square, CPSS). 为了描述简便, 我们用 "方割" 来表示用小正方形分割大的正方形或者长方形.