Probabilistic techniques 2 (NTIN095)

Robert Šámal and Matas Šileikis

Class about probability meeting discrete math, a loose follow-up to Pravděpodobnostní techniky (NTIN022).

We will see more advanced tools to prove things using probability. We will also look at properties of random objects, such as random graphs in various forms.

2 hours of lecture plus (take-home) exercises


Planned topics


First set now with HINTS
Second set now with HINTS

Class Notes

First class

Log from classes

1. class 24.2.2017
Basic models of random subsets: uniform and binomial; their asymptotic equivalence (with proofs); definitions of thresholds and sharp thresholds; Theorem that every monotone property has a threshold (without a proof).
2. class 3.3.2017
Threshold for existence in $G(n,p)$ and $G(n,M)$ of threshold of a fixed graph $H$. Description of evolution of random graphs. Galton-Watson branching process, probabillity generating function. Theorem about extinction probabillity.
3. class 10.3.2017
Proof of result about the evolution of giant component.
4. class 17.3.2017
Talagrand inequality: Motivation -- concentration inequalities. Formulation and proof of the Talagrand inequality.
5. class 24.3.2017
More applicable version of Talagrand inequality: certifiable Lipschitz functions. Applications.
no class 31.3.2017
no class 7.4. and 14.4.2017 (spring school and Eastern)
6. class 20.4.2017
Application of Talagrand: improvement of Brooks' theorem for triangle-free graphs.
7. class 27.4.2017
Conditional expectation. Martingales. Proof of Azuma inequality. Doob martingale.
8. class 5.5.2017
Properties of Doob martingale. Applications.
9. class 12.5.2017
Chromatic number of random graph.
10. class 19.5.2017
Algorithmic LLL -- proof following the original paper. (Just the sequential algorithm.) Question to be resolved: what is the relation to the proof on various blogs? I'm not quite convinced by this particular one.
11. class 26.5.2017
Plan: Random regular graphs (MS).