Mathematics / advanced
Probabilistic combinatorics
Prove the existence and typical structure of discrete objects using randomness, concentration, and dependency arguments.
Your route through mathematics
Follow the path or begin with a question. Every lesson is open.
Your place, at your pace. Progress is optional and saved only in this browser when available.
Read / explore / reason
Inside this module
Module 01 advanced
Probabilistic combinatorics
Prove the existence and typical structure of discrete objects using randomness, concentration, and dependency arguments.
- 01
First moments and existence certificates
Turn a count of obstructions into a positive probability of a valid discrete construction.
28 min - 02
Second moments and Paley–Zygmund
Control the cost of overlap and turn first moments into quantitative lower bounds.
28 min - 03
Random graph thresholds and components
Separate edge, triangle, giant-component, and connectivity scales in independent-edge graphs.
28 min - 04
Chernoff bounds in combinatorial models
Use exponential moments to control many simultaneous deviations while preserving independence assumptions.
28 min - 05
The Lovász local lemma and dependency graphs
Replace a global small-error requirement with local control of rare interacting events.
28 min - 06
Alteration and randomized rounding
Repair a random candidate and account jointly for retained value and repair cost.
28 min - 07
Martingale exposure and Azuma’s inequality
Reveal randomness gradually and bound changes in conditional predictions rather than assuming independent increments.
28 min - 08
Random regular graphs and configuration models
Distinguish uniform half-edge matchings, their multigraph projections, and conditioning on simplicity.
28 min - 09
Janson inequalities and subgraph counts
Use independent underlying choices and an explicit overlap sum to bound the absence of dependent patterns.
28 min - 10
Random processes and the differential equation method
Convert conditional drift into an ODE and control the stochastic error uniformly before a valid stopping boundary.
28 min