Mykhaylo Tyomkyn

Lecture on Probabilistic techniques (NTIN022) 2024/25

Lecture: Wed, 14:00, S4. Exercise classes: Wed, 15:40, S1 (TA Tomáš Hons, Tung Anh Vu). Webpage for exercise classes.

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

Exams

Exam times will be scheduled by individual arrangement. Please let me know by email: tyomkyn@kam , where `kam' stands for kam.mff.cuni.cz, when you are available to take an exam.

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 an old webpage.

Organization remark

Exercise classes will be based on individual work of the attendants (homeworks; they are supposed to be solved during the semester).

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

Topics covered

2 Oct: Introduction. A proof that $R(k,k) > 2^{k/2}$, 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. Further applications of the basic probabilistic method: satisfiablility of boolean formulas (equivalently, 2-colourability of hypergraphs), dominating sets in a graph with given min-degree. [AS 1]
9 Oct (double lecture): Applying expectation of the random variable: Tournaments with many Hamiltonian paths; MAXCUT - existence of a cut in a graph with many edges (with derandomization); balancing vectors - $\pm$ sums of unit vectors can be achieved both high and low (with derandomization); large sum-free subsets. Alterations: weak Turán theorem; an improved lower bound on $R(k,k)$. [MV 3, 4.1, AS 1.4, 2.1, 2.2, 2.4, 3.1, 3.2].
Existence of graphs of large girth and chromatic number. An application of alterations in combinatorial geometry: the Heilbronn triangle problem.
(non-examinable:) Existense of dense triple systems with no $k+2$ vertices inducing $k$ or more edges. [MV 4.2, AS 3.3, I will later provide notes for the last part]
16 Oct: No lecture
23 Oct: The second moment method: variance of a random variable, standard deviation, covariance. Variance of a sum of random variables. Chebyshev's inequality. Lower bound for the middle binomial coefficient. Threshold functions - triangle counts in G(n,p). The threshold function for containment of a balanced graph $H$. [MV 5.1, 5.2, 5.3, AS 4]
30 Oct: More on the second moment method: the clique number of $G(n,1/2)$. A randomized algorithm for computing the median [MV 5.4, MU 3.4]
6 Nov: Lovász local lemma: statement and proof. The symmetric version. General implies symmetric. Applications: an improved lower bound on $R(k,k)$, 2-colourable hypergraphs revisited. [MV 6.1, 6.2, AS 5.1, 5.2, 5.3]
13 Nov: Applications of the Lovász local lemma: existence of injective functins (joke), cycles of length divisible by $k$ in directed graphs, colourings of the reals: colourful translates. A sketch of an application of an asymmetric version: a lower bound on the Ramsey numbers R(3,k). [MV 6.3, 6.4, 6.5, AS 5.2, 5.3]
20 Nov: Basic Chernoff's bound. Applications: max degree in $G(n,1/2)$, combinatorial discrepancy. A more general variant of Chernoff's bound. [MV 7.1, 7.2]
27 Nov: Application of Chernoff to randomized rounding for the k-matching problem. The anti-concentration counterpart to Chernoff, and an application: a lower bound on discrepancy of set systems. [MV 7.2, 7.3]
4 Dec (PLAN): Markov chains: definition, representation by digraphs and by matrices. Symmetric random walks, Gambler's ruin. Algorithms for 2-SAT and for 3-SAT (will be finished next time). [MU 7.1]