拉姆齐定理与拉姆齐数
拉姆齐定理保证任何足够大的二染色完全图都包含一个单色团，而拉姆齐数则量化了“足够大”的程度。
用 PaperMind 寻找选题即将推出Find papers & topics
Tools & resources
Learn & explore
视频即将推出
Definition
拉姆齐数 R(s,t) 是最小的整数 n，使得对 n 个顶点的完全图的边进行任意红蓝染色，都包含一个 s 个顶点的红色团或一个 t 个顶点的蓝色团。
Scope
本主题涵盖拉姆齐定理的图论形式、拉姆齐数 R(s,t) 的定义、经典的几个小案例（如 R(3,3)=6）、Erdos-Szekeres 上界和 Erdos 的概率下界，以及向多色和超图拉姆齐数的推广。它是拉姆齐理论的定量核心。
Core questions
- 一个完全图必须有多大才能强制出现给定大小的单色团？
- 拉姆齐数的已知精确值和界限有哪些？
- 概率论证如何给出拉姆齐数的下界？
- 该定理如何推广到多种颜色和超图？
Key concepts
- 图的拉姆齐定理
- 拉姆齐数 R(s,t)
- 单色团
- Erdos-Szekeres 界
- 概率下界
- 多色和超图拉姆齐数
Key theories
- Erdos-Szekeres 上界
- 拉姆齐数是有限的，并且受限于 R(s,t) 至多为 s+t-2 选 s-1 的二项式系数，这是一个基于递推的界限，通过明确的估计证明了拉姆齐定理。
- Erdos 的概率下界
- 通过计算随机染色中预期单色团的数量，Erdos 在 1947 年表明对角拉姆齐数 R(s,s) 至少呈指数增长，这是概率方法的开创性应用。
Clinical relevance
通过拉姆齐数下界引入的概率方法成为组合学和理论计算机科学的核心工具，而拉姆齐型保证则支撑着通信和数据结构的下界。
History
Erdos 和 Szekeres 在 1935 年研究凸多边形时重新发现并量化了拉姆齐定理；Erdos 在 1947 年提出的随机染色下界开创了概率方法。
Key figures
- Frank Ramsey
- Paul Erdos
- George Szekeres
Related topics
Seminal works
- graham1990
Frequently asked questions
- 为什么 R(3,3) 等于六？
- 在任意六个人中，总有三个人是彼此认识的，或者三个人是彼此陌生的，而五个人则可以安排成既没有彼此认识的三人也没有彼此陌生的三人，所以六是精确的阈值。
- 拉姆齐数有精确值吗？
- 只有少数几个是精确已知的；即使是 R(5,5) 也尚未解决，目前的知识只能将其范围缩小，因为搜索空间增长过快，无法通过计算确定。