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

Literature

N. Alon, J. Spencer: The Probabilistic Method
S. Janson, T. Łuczak, A. Ruciński: Random Graphs, J. Wiley and Sons
A. Frieze, M. Karoński: Introduction to Random Graphs, Cambridge University Press available online (with some corrections)
B. Bollobás: Random Graphs, Cambridge University Press

Planned topics

equivalence of graphs G(n,p) and G(n,m)
emergence of the giant component in the Erdos-Renyi graph
branching processes
Martingales
Concentration inequalities (Azuma, Talagrand, Jansson)
concentration of Chromatic number in Erdos-Renyi graph
algorithmic version of Local Lovász Lemma
Local Cut Lemma (aka entropy compression)
random regular graphs (configuration model, existence of Hamilton cycles)
multistage random choices (Rödl nibble), such as Johansson's bound $O(D/\log D)$ for chromatic number of graphs with maximum degree $D$, no triangles and no four-cycles.
upper tail for number of triangles

Exercises

First set now with HINTS
Second set now with HINTS
Results

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.
EXERCISE SESSION AFTER CLASS
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).