Probabilistic techniques 2 (NTIN095)
Robert Šámal and Mikhaylo Tyomkyn
Class about probability meeting discrete math, a loose followup to
Probabilistic techniques (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
Class will be held in English (the part taught by RS can be in Czech, if there is nobody interested in it
who has does not understand Czech language).
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
 M. Molloy, B. Reed: Graph Colouring and the Probabilistic Method, Springer
Planned topics
 Correlation inequalities (HarrisFKG, BK)
 Thresholds (KahnKalai conjecture)
 Quasirandomness (ChungGrahamWilson)
 Random regular graphs (configuration model, existence of Hamilton cycles)
 Martingales
 Concentration inequalities (Azuma, Talagrand, Jansson)
 Concentration of Chromatic number in ErdosRenyi graph
 Branching processes
 Algorithmic version of Local Lovász Lemma
Exercises
First set
Solve the problems marked by (*) and submit for grading. (All are worth the same number of points.)
Problems submitted after Mar 14 have 10 % penalty.
Second set
Second set  Now with a reference statements of the bounds we covered.
Some of them even in slightly more general versions (you may use those
if you wish).
Problem 1 has now corrected statement  the bound for distance was incorrect before.
Third set
Third set. There won't be any more inperson exercise session. But after you have solved some of the problems
(or no longer need any more points) we are available to discuss the problems, if you will be interested.
Log from classes
 1. class 14.2.2023 [MT]

Correlation inequalities. Introduction: the HarrisKleitman
lemma for the uniform measure on the boolean cube. The four functions
theorem: statement, proof and first applications. Distributive lattices,
the four functions theorem thereon.
 2. class 21.2.2023 [MT]

The FKG inequality on distributive lattices. An application:
proof of the XYZtheorem on linear extensions of finite posets.
 3. class 28.2.2023 [MT + RS]

[MT] Disjoint occurrence of events: the BK inequality (statement and proof), Reimer's inequality (statement).
[RS] Martingales  basic definition and motivation. Azuma inequality with most of the proof.
Source: AlonSpencer.
 4. class 7.3.2023 [RS]

Full proof of Azuma.
Applications: concentration of chromatic number of random graph $G(n,p)$.
Huge strenghtening of this for the case $p = n^{\alpha}$ with $\alpha > 5/6$.
Source: AlonSpencer.
 5. class 14.3.2023 [RS]

General framework for Azuma inequality.
Three applications (range of a random function, norm of a random sum,
variant of isoperimetric inequality).
Talagrand inequality: definition of certifiability, statement of the theorem.
Source: AlonSpencer.
 6. class 21.3.2023 [RS]

Talagrand inequality: proof, one application.
Source: AlonSpencer.
EXERCISE SESSION AFTER CLASS
 6. class 28.3.2023 [RS]

Talagrand inequality: end of proof.
KimVu polynomial concentration (without proof).
Notes: Holder inequality indeed holds also for $p=\infty, q=1$ (and vice versa), see wiki.
Source: AlonSpencer.
 7. class 4.4.2023 [RS]

Application of Talagrand: improvement of Brooks' theorem for trianglefree graphs of high enough max. degree.
Source: Molloy & Reed.
 8. class 11.4.2023 [RS]

Poisson paradigm: Janson Inequalities.
Basic application (probability that $G(n,c/n)$ is trianglefree tends to a limit $e^{c^2/6}$).
More complex application: clique number and the chromatic number of random graph.
Short mention: algorithmic version of local lemma works!
 9. class 18.4.2023 [MT]

Thresholds: BollobasThomason theorem. Probability vs. expectation
thresholds. KahnKalai conjecture/ParkPharm theorem: statement and
examples. (Source: Chapters 1 and 15 of FriezeKaronski
and paper by Park and Pham.
 10. class 25.4.2023 [RS]

Random regular graphs.
 11. class 2.5.2023 [MT]

KahnKalai conjecture.
 12. class 9.5.2023 [MT]

Quairandomness. The ChungGrahamWilson theorem.
 13. class 16.5.2023 [MT]

Pseudorandomness in the sparse regime: $(n,d,\lambda)$graphs
and their properties. The expander mixing lemma. the AlonBoppana bound.