研究生一年级Discrete Mathematics课程已上线
The probabilistic method
Proving existence by showing that a random object has the desired property with positive probability: Erdős's lower bound for Ramsey numbers, linearity of expectation, the second-moment method, the Lovász local lemma and concentration inequalities.
math.discrete.probabilistic-method
前置知识
44 项必需的前置知识（一直追溯到底）
你将学会
- Prove Erdős's bound R(k, k) > 2^(k/2) for k ≥ 3 using a random colouring.
- Use linearity of expectation and deletion arguments to prove existence results.
- Apply the Lovász local lemma and Chernoff bounds.
定义
- First-moment method: if X takes non-negative integer values and E[X] < 1, then P(X = 0) > 0.
- Lovász local lemma (symmetric form): if each of a collection of bad events has probability at most p and is mutually independent of all but at most d of the others, and ep(d + 1) ≤ 1, then with positive probability none of the bad events occurs.
定理
- R(k, k) > 2^(k/2) for every k ≥ 3 (Erdős, 1947).
- There are graphs with arbitrarily large girth and arbitrarily large chromatic number (Erdős, 1959).
常见误解
- Thinking a probabilistic existence proof gives an efficient construction; explicit constructions are often unknown.
通向
可选发现
- Computational complexity Derandomisation asks when random constructions can be replaced by efficient deterministic ones; the algorithmic local lemma of Moser and Tardos is one success.
延伸阅读
- Noga Alon and Joel H. Spencer, The Probabilistic Method (1992)