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

Lecture: Tue, 12:00, zoom, Exercise classes: Tue, 14:00, platform to be announced (TA Denys Bulavka and Matěj Konečný). Webpage for exercise classes: web of Matěj Konečný.

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

## Exams

Exam terms are scheduled in SIS. (Most of them are with Martin Klazar with one exception with Martin Tancer.) Distant exam is possible on request, write to both of us please (preferably with a reason why do you need a distant exam), and we will find some agreement.

## 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

Probabilistic techniques are a major tool of discrete mathematics, they are also frequently used in design and analysis of algorithms and other areas of computer science. The lecture introduces basic notions, methods, and estimates and illustrates them on examples from computer science and discrete mathematics.
If you are interested in more details about the lecture, you may check .

### Lecture notes

[MV] J. Matoušek, J. Vondrák: The Probabilistic Method ITI Series (preprints Institute of Computer Science, MFF UK), 2002-087; available in the library of MFF UK or you may get a revised version online

### Syllabus

Basic notions and methods: events, expected value and its linearity, conditional probability, Bayes' rule.
Basic inequalities and estimates: Markov's a Chebyshev's inequality, Chernoff-type estimates.
Probabilistic method: basic method and alteration method, Lovász local lemma.
Advanced techniques: balls and bins model, basic estimates and applications, Markov chains, stationary distribution, basic continuous distributions as limits of discrete ones, properties and applications. Illustration of the methods on examples from various areas of discrete mathematics and theoretical computer science.

### 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

If you are interested to get a video of any of the lectures, write me (Martin Tancer) that you want to get it. I do not want to make videos publicly available. You can find my email on my homepage.

## 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.