Probabilistic techniques 2 (NTIN095)
Robert Šámal and Matas Šileikis
Class about probability meeting discrete math, a loose followup 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 (takehome) 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 ErdosRenyi graph
 branching processes
 Martingales
 Concentration inequalities (Azuma, Talagrand, Jansson)
 concentration of Chromatic number in ErdosRenyi 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 fourcycles.
 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. GaltonWatson
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 trianglefree 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).