主题
Search

拉姆齐定理

DOWNLOAD Mathematica Notebook下载 Wolfram Notebook

拉姆齐定理是 Dilworth 引理的推广，它指出对于每对正整数 k 和 l，都存在一个整数 R(k,l) (称为拉姆齐数)，使得任何具有 R(k,l) 个节点的图都包含至少有 k 个节点的团或至少有 l 个节点的独立集。

该定理的另一种表述是，对于整数 k,l>=2，存在一个最小正整数 R(k,l)，使得无论如何对完全图 K_(R(k,l)) 进行双色着色，它都将包含一个绿色子图 K_k 或一个红色子图 K_l。

该定理的第三种表述指出，对于所有 k in N，都存在一个 l in N，使得任何具有 l 个图顶点的完全有向图都包含一个具有 k 个图顶点的完全顶点传递子图。

例如，R(3,3)=6 且 R(4,4)=18，但 R(5,5) 仅已知在 43<=R(5,5)<=49 和 102<=R(6,6)<=165 的范围内。

确实如此

R(k,l)<=R(k-1,l)+R(k,l-1)

如果 k,l>=3。

另请参阅

Dilworth 引理, 狄利克雷盒原理, 极图理论, 图着色, 自然独立现象, 聚会问题, 拉姆齐数, 拉姆齐理论

使用 探索

参考文献

Borwein, J. 和 Bailey, D. Mathematics by Experiment: Plausible Reasoning in the 21st Century. Wellesley, MA: A K Peters, 页 33-34, 2003.Graham, R. L.; Rothschild, B. L.; 和 Spencer, J. H. Ramsey Theory, 2nd ed. New York: Wiley, 1990.Mileti, J. "Ramsey's Theorem." http://www.math.uiuc.edu/~mileti/Museum/ramsey.html.Spencer, J. "Large Numbers and Unprovable Theorems." Amer. Math. Monthly 90, 669-675, 1983.

在 上被引用

拉姆齐定理

请引用为

Weisstein, Eric W. "拉姆齐定理。" 来自 Web 资源。 https://mathworld.net.cn/RamseysTheorem.html

主题分类