Probabilistic Combinatorics

Module aims

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

Course outline

1. 01 The probabilistic method 20h

   Learning result Prove existence by showing a random object has positive probability of a property.

   Formative check Written derivation

2. 02 First moment 20h

   Learning result Use expectation to bound a combinatorial quantity from above or below.

   Formative check Written derivation

3. 03 Second moment and alteration 25h

   Learning result Apply a second-moment or deletion argument and state when first moment is not enough.

   Formative check Written derivation

4. 04 Local lemma 20h

   Learning result Check dependency-degree hypotheses and conclude a positive probability of avoiding all bad events.

   Formative check Four-option check

5. 05 Concentration for combinatorial sums 25h

   Learning result Apply a Chernoff or bounded-difference bound to a combinatorial function.

   Formative check Written derivation

6. 06 Random graphs (taught grain) 20h

   Learning result State a threshold phenomenon and the probability model G(n,p).

   Formative check Four-option check

7. 07 Synthesis 20h

   Learning result Write a first-moment existence argument with explicit events; keep a concentration tail as a separate claim when both are used.

   Formative check Written derivation

Learning results

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

Subject skills

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

Transferable skills

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