48 lines
1.3 KiB
Markdown
48 lines
1.3 KiB
Markdown
---
|
||
title: "Ramsey Numbers（拉姆齐数）"
|
||
created: 2026-05-11
|
||
updated: 2026-05-11
|
||
type: concept
|
||
tags: [combinatorics, graph-theory, extremal-combinatorics]
|
||
sources: [[ramsey-numbers-survey]]
|
||
---
|
||
|
||
# Ramsey Numbers（拉姆齐数）
|
||
|
||
## 定义
|
||
|
||
拉姆齐数 R(r,s) 是满足以下性质的最小正整数 n：对完全图 K_n 的任意红蓝二色边着色，必然包含一个红色 K_r 或一个蓝色 K_s。
|
||
|
||
等价表述：任意 n 顶点图或其补图中必含 r-团或 s-独立集的最小 n。
|
||
|
||
## 核心性质
|
||
|
||
- **对称性**：R(r,s) = R(s,r)
|
||
- **边界**：R(k,2) = k
|
||
- **递归上界**：R(r,s) ≤ R(r-1,s) + R(r,s-1)（鸽巢原理）
|
||
|
||
## 已知精确值
|
||
|
||
| k | R(k) | 来源 |
|
||
|---|------|------|
|
||
| 3 | 6 | 聚会问题 |
|
||
| 4 | 18 | Greenwood-Gleason 1955 |
|
||
| 5 | 43-48 | Exoo(↓), McKay-Radziszowski(↑) |
|
||
| 6 | 102-165 | 精确值未知 |
|
||
|
||
## 一般界
|
||
|
||
- **下界**（Erdős 1947）：R(k) > 2^{k/2}
|
||
- **上界**（Conlon 2009）：R(k) ≤ 4^k / √k
|
||
- **指数鸿沟**：底数 √2（≈1.414）到 4 的差距是核心未解决问题
|
||
|
||
## 非平凡渐近阶
|
||
|
||
R(3,k) = Θ(k²/log k) 是少数渐近阶已完全确定的例子（Ajtai-Komlós-Szemerédi 1980 + Kim 1995）。
|
||
|
||
## 相关概念
|
||
|
||
- [[diagonal-ramsey-number|对角拉姆齐数]]
|
||
- [[ramsey-theory|拉姆齐理论]]
|
||
- [[hypergraph-ramsey-number|超图拉姆齐数]]
|