主題
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.tw/RamseysTheorem.html

主題分類