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
- 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
- equivalence of graphs G(n,p) and G(n,m)
- emergence of the giant component in the Erdos-Renyi graph
- branching processes
- 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
First set now with HINTS
Second set now with HINTS
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
- 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
I'm not quite convinced by this particular one.
- 11. class 26.5.2017
Plan: Random regular graphs (MS).