Tereza Klimošová, Mykhaylo Tyomkyn
Lecture: Mon, 9:00, S1.
Exercise classes: Mon, 17:20, S6 (TA Denys Bulavka).
Webpage for exercise classes.
List of topics covered by lectures is at the bottom of this webpage.
Zkoušky/Exams
Exam times will be scheduled by individual arrangement. Please let Mykhaylo Tyomkyn 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),
2002087; 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, Chernofftype 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
 Oct 3 (TK)

Overview of basic notions in probability: probability space, union bound. ErdősRényi random graph.
Probabilistic approach for a proof of existence of certain graphs:
$R(k,k) > 2^{k/21}$, 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. Continuation with basic notions: Independent
events, conditional probability, law of total probability. Application: CNF formula where every clause contains $k$ different literals and the number of clauses is less than $2^k$ is satisfiable. [MV 1, 2.1, AS 1.1]
 Oct 10 (TK)

ErdősKoRado theorem. Further probabilistic concepts: random variables, expectation, independent random variables, linearity of expectation, product of expectations of independent random variables, indicators of random events. Applications: expected number of fixed points in a random permutation, tournaments with many Hamiltonian paths. [MV 1, 2.3, 3.1, 3.2, AS 2.1]
 Oct 17 (TK)

Further applications of linearity of expected value: balancing vectors, $\pm$ sums of unit vectors can
be achieved both high and low. With derandomization: MAXCUT  existence of a cut in a graph with many edges; MAXSAT  satisfying many clauses in a formula. Alterations: weak Turán theorem. Markov's inequality. [MV 3, 4.0
4.1, AS 2.1, 2.2, 2.4, your own notes (MAXCUT, derandomization (see AS 15 for idea of derandomization on a different example)]
 Oct 24 (TK)

Showing the existence of graphs with arbitrarily high
chromatic number and girth.
Geometric/continuous application of alterations: Points in unit square and
triangles of small area. [MV 4.2, AS 3.3]
 Oct 31 (TK)

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. Threshold functions  preliminaries: triangle counts in G(n,p)  expectation and variance, to be continued during the next lecture. [MV 5.1, 5.2, 5.3, your own notes for matrix
multiplication]
 Nov 7 (TK)

Threshold function definition. Threshold function for containment of a balanced graph $H$. Lovász local
lemma, symmetric version, general version (no proof). General
implies symmetric. [MV 5.3, 6.1]
 Nov 14 (TK)

Three applications of Lovász local lemma (symmetric version): routing in a graph by edge
disjoint paths, twocolorability of a sparse hypergraph, and cycles of length
divisible by $k$ in directed graphs. A sketch of an application of an asymmetric version: lower bound on Ramsey number R(3,l). [MU 6.7.1 (with slightly different
constants), MV 6.26.3, your own notes for the application of asymmetric LLL]
 Nov 21 (MT)

Basic Chernoff's
bound. Applications: max degree in $G(n,1/2)$, combinatorial discrepancy. A more general variant of Chernoff's
bound.
[MV 7.17.2]
 Nov 28 (MT)

Application of Chernoff to randomized rounding for the kmatching problem.
Markov chains: definition, representation by finite automata and by matrices. Algorithms for 2SAT and for 3SAT (will be finished next time).
[MV 7.2, MU 7.1]
 Dec 5 (MT)

Finishing 2SAT and 3SAT algorithms. More Markov chains: accesible/communicating states, states transient/recurrent, and null/positive recurrent, examples.
[MU 7.1, 7.2]
 Dec 12 (MT)

Periodic/aperiodic states/MC. Ergodic states/MC. Example: Gambler's ruin. Theorem about stationary distribution of a Markov chain: proof based on these notes by Prof Sgall, and these by Prof Whitt (Columbia).
[MU 7.2, 7.3]
 Dec 19 (MT)

Balls and bins: birthday paradox, maximum load, bucket sort. Poisson distribution.
[MU 5.15.3]
 Jan 2 (MT)

Balls and bins: the Poisson approximation. A lower bound on max load. handwritten notes
[MU 5.4]