Martin Klazar, Martin Tancer

Lecture on Probabilistic techniques (Přednáška Pravděpodobnostní techniky (NTIN022)) 2020/21

List of topics covered by lectures is at the bottom of this webpage.

Exams

Important infromation for online teaching

• You need to join to the lectures via Zoom: The meeting id is 982 7073 3410. For the first time, you also need to register to the meeting via this link. Finally, you should also know a password for joning the meeting. If you have registered for the class via SIS by Monday, Sep 28, 5:30 PM, then you should get an email from me with the password. If you did not register or you did not get the email by Monday, Sep 28, 10 PM, then send me an email asking for the password, please.
• The initial lectures will be given by Martin Tancer. I plan to give a lecture with slides via a Zoom room. The slides will also gradually appear at the bottom of this webpage. (Please note that in this period I have to prepare slides for several lectures a bit hastily, thus the slides may contain typos. I will appreciate a lot to let me know if you find some typos---it will help other students.)
• Please, ask many questions during the lecture. It is harder to check how do you understand the topic via an online platform.

Lecture contents

Anotation

Lecture notes

Syllabus

References

• [AS] N. Alon, J. Spencer: The Probabilistic Method, J. Wiley and Sons 1993, 2008, 2015.
• [MU] M. Mitzenmacher, E. Upfal: Probability and Computing: Randomized Algorithms and Probabilistic Analysis, Cambridge University Press, 2005.
• [MR] R. Motwani, P. Raghavan: Randomized algorithms, Cambridge University Press, 1995.
• [O'D] R. O'Donell: Probability and Computing lecture notes
• J. Spencer: Ten lectures on the probabilistic method, SIAM, 1987
• One chapter of J. Matoušek, J. Nešetřil: Invitation to Discrete Mathematics. (covers just a first part of the class).

Lecture recordings

Topics covered

Sep 29 (MT) Slides (There is an important correction on the last slide in the definition of independent events for more than two events. May be very useful when solving homework problems.)

Motivation. Overview of basic notions in probability: probability space, examples, union bound. Probabilistic approach for a proof of existence of certain graphs: $R(k,k) > 2^{k/2-1}$, where $R(k,k)$ is the Ramsey number, the minimal number of vertices that guarantees that a graph has an independent set or a clique with $k$ vertices. Estimates of factorial and binomial coefficients, $e^x \geq 1+x$. Continuation with basic notions: Independent events, conditional probability. [MV 1, 2.1, AS 1.1]

Oct 6 (MT) Slides (Some extensions/corrections when compared with the lecture: Added a missing assumption in proposition about satisfiability (you can try to figure out yourself that distinct literals would be also sufficient). Added an explanation for a step in the Erdős-Ko-Rado theorem that we discussed during the lecture--this is an extra slide below the proof).

Satisfiability of CNF formulas. Erdős-Ko-Rado theorem. Further notions: random variables, expectation, linearity of expectation, independent random variables, product of expectation for independent random variables, indicators. Application: number of fixed points in a random permutation. [MV 1, 2.3, 3.1, AS 2.1, slides (CNF formulas)]

Oct 13 (MT) Slides (With minor corrections after the lecture.)

Further applications of linearity of expected value: tournaments with many Hamiltonian paths; MAXSAT - satisfying many clauses in a formula; MAXCUT - existence of a cut in a graph with many edges (derandomization of MAXCUT, sketched also MAXSAT); balancing vectors, $\pm$ sums of unit vectors can be achieved both high and low. Alterations: weak Turán theorem. [MV 3, 4.1, AS 2.1, 2.2, 2.4, slides/lecture recording (MAXCUT, derandomization)]

Oct 20 (MT) Slides (With minor corrections after the lecture.)

Markov's inequality. Showing the existence of graphs with arbitrarily high chromatic number and girth. Bayes theorem. Geometric/continuous application of alterations: Points in unit square and triangles of small area. [MV 4.0, 4.2, AS 3.3, slides (Bayes)]

Oct 27 (MT) Slides (With a minor correction after the lecture.)

Testing $AB = C$ for three given $n \times n$ matrices faster than matrix multiplication. Variance, standard deviation, covariance. Variance of a sum of random variables. Chebyshev's inequality. Lower bound for a middle binomial coefficient. [MV 5.1, 5.2, slides for matrix multiplication]

Nov 3 (MT) Slides (With several corrections found during the lecture, the most noticeable are the corrections in the definition of the threshold function.)

Threshold functions. The function $1/n$ is a threshold function for triangle containment. Threshold function for containment of a balanced graph $H$. [MV 5.3]

Nov 10 (MT) Slides (With several correction found during the lecture, the most noticeable is the independence of an event of other events and the conclusion in the symmetric local lemma.)

Dependency graph. Lovász local lemma, symmetric an general version. Shown how general implies symmetric but otherwise left without proof. Three applications of Lovász local lemma: two-colorability of a sparse hypergraph, routing in a graph by edge disjoint paths, and cycles of length divisible by $k$ in directed graphs. (In the last case, the bound on the degree in the dependency graph only sketched.) [MV 6.1--6.3, MU 6.7.1 (with slightly different constants)]

For the remaining topics, see the webpage of the second lecturer.