Probabilistic Combinatorics

模块目标

Turn a random construction into a deterministic existence proof, and quantify how sharply a combinatorial quantity concentrates.

课程大纲

1. 01 The probabilistic method 20h

   学习结果 Prove existence by showing a random object has positive probability of a property.

   形成性检查 书面推导

2. 02 First moment 20h

   学习结果 Use expectation to bound a combinatorial quantity from above or below.

   形成性检查 书面推导

3. 03 Second moment and alteration 25h

   学习结果 Apply a second-moment or deletion argument and state when first moment is not enough.

   形成性检查 书面推导

4. 04 Local lemma 20h

   学习结果 Check dependency-degree hypotheses and conclude a positive probability of avoiding all bad events.

   形成性检查 四选一检查

5. 05 Concentration for combinatorial sums 25h

   学习结果 Apply a Chernoff or bounded-difference bound to a combinatorial function.

   形成性检查 书面推导

6. 06 Random graphs (taught grain) 20h

   学习结果 State a threshold phenomenon and the probability model G(n,p).

   形成性检查 四选一检查

7. 07 Synthesis 20h

   学习结果 Write a first-moment existence argument with explicit events; keep a concentration tail as a separate claim when both are used.

   形成性检查 书面推导

学习结果

Apply first/second moment, alteration, or Lovász Local Lemma with each probability model and hypothesis stated explicitly.

学科技能

Probabilistic method, first and second moments, alteration, concentration, random graphs at taught-MMath grain.

可迁移技能

Keep existence proofs separate from constructive algorithms; name the probability space.