# 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

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).