1.0 KiB
1.0 KiB
title, created, updated, type, tags, sources
| title | created | updated | type | tags | sources | |||||
|---|---|---|---|---|---|---|---|---|---|---|
| van der Waerden Theorem | 2026-05-11 | 2026-05-11 | concept |
|
|
van der Waerden Theorem
定义
对正整数的任意有限着色，必存在任意长的单色等差数列。
形式化：对任意正整数 r 和 k，存在最小 W(r,k)，使得对 {1,...,W(r,k)} 的任意 r-着色，必存在长为 k 的单色等差数列。
历史地位
- 1927：Bartel van der Waerden 证明，是最早的 Ramsey 型结果之一
- 密度推广：szemerédi-regularity-lemma（1975）将其从着色条件加强为密度条件
- 峰顶：green-tao-theorem将这一结论应用于素数集
证明精神
原始证明使用双重归纳法，其递归结构预示了后来 Ramsey 理论中"从大到小逐步提取子结构"的标准策略。