1.3 KiB
1.3 KiB
title, created, updated, type, tags, sources
| title | created | updated | type | tags | sources | |||||
|---|---|---|---|---|---|---|---|---|---|---|
| Probabilistic Method（概率方法） | 2026-05-11 | 2026-05-11 | concept |
|
|
Probabilistic Method（概率方法）
定义
概率方法是 Paul Erdős 于 1947 年引入的证明技术：为证明具有某种性质的组合对象存在，构造一个概率空间，并证明该对象以正概率满足性质——由此推出存在性，无需显式构造。
在 Ramsey 理论中的应用
对 K_n 的边进行随机二色着色（每条边独立以 1/2 概率染红），计算出现单色 K_k 的期望数量。当该期望 < 1 时，存在无单色 K_k 的着色 → R(k) > n。
结果：R(k) > 2^{k/2}——这一下界至今未被构造性方法超越。
核心推广
lovasz-local-lemma（1975）：处理大量相关事件同时不发生的情形，在 Ramsey 理论中用于证明更强的存在性结果。
历史意义
概率方法不仅解决了 Ramsey 问题，还催生了整个 random-graph-theory（Erdős-Rényi 模型），深刻改变了组合数学的方法论——从"构造"到"证明存在"的范式转变。