Probabilistic techniques 2 (NTIN095)

Robert Šámal and Mikhaylo Tyomkyn

Class about probability meeting discrete math, a loose follow-up 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 (take-home) 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

Planned topics


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 in-person 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 Harris-Kleitman 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 XYZ-theorem 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: Alon-Spencer.
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: Alon-Spencer.
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: Alon-Spencer.
6. class 21.3.2023 [RS]
Talagrand inequality: proof, one application. Source: Alon-Spencer.
EXERCISE SESSION AFTER CLASS
6. class 28.3.2023 [RS]
Talagrand inequality: end of proof. Kim-Vu polynomial concentration (without proof). Notes: Holder inequality indeed holds also for $p=\infty, q=1$ (and vice versa), see wiki. Source: Alon-Spencer.
7. class 4.4.2023 [RS]
Application of Talagrand: improvement of Brooks' theorem for triangle-free 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: Bollobas-Thomason theorem. Probability vs. expectation thresholds. Kahn-Kalai conjecture/Park-Pharm theorem: statement and examples. (Source: Chapters 1 and 15 of Frieze-Karonski and paper by Park and Pham.
10. class 25.4.2023 [RS]
Random regular graphs: Configuration model, basic properties (number of short cycles in the graph). Source: Chapter 11.1 of Frieze-Karonski.
11. class 2.5.2023 [MT]
Kahn-Kalai conjecture.
12. class 9.5.2023 [MT]
Quairandomness. The Chung-Graham-Wilson theorem.
13. class 16.5.2023 [MT]
Pseudorandomness in the sparse regime: $(n,d,\lambda)$-graphs and their properties. The expander mixing lemma. the Alon-Boppana bound.