Robert Šámal, Martin Tancer
Lecture: Mo 15:40 in S4,
Exercise classes: Mo 17:20 in S6.
Webpage for exercise classes: web of Jan Voborník.
List of topics covered by lectures is at the bottom of this webpage.
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
the topics covered last
year (in Czech).
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.
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

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.

J. Spencer: Ten lectures on the probabilistic method, SIAM, 1987

kapitola ze skript J. Matoušek, J. Nešetřil: Kapitoly z diskrétní matematiky
(pokrývá jen úvodní část přednášky)
Topics covered
 Oct 2 (MT)

Probabilistic approach for a proof of existence of certain graphs:
$R(k) > 2^{k/2}$, where $R(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.
Overview of basic notions in probability: probability space, union bound,
independent events, conditional probability. Estimates of
factorial and binomial coefficients, $1 + x \leq e^x$. Expected value (at the
moment only for a finite probability space).
 Oct 9 (MT)

Further applications of probabilistic approach: CNF formulas where each clause
has $k$ literals and number of clauses is less than $2^k$ is satisfiable;
ErdősKoRado theorem.
Further basic notions from probability theory: random variables; expected
value; independent variables; linearity of expected value; for independent
variables, product of expected values is the expected value of product.
Applications of linearity of expected value: Number of fixed points in a random
permutation.
 Oct 16 (MT)

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.
 Oct 23 (MT)

Markov's inequality. An existence of graphs with arbitrarily high
chromatic number and girth. Bayes theorem. Application: testing $AB = C$ for
three given $n \times n$ matrices faster than matrix multiplication.
Geometric/continuous application of alterations: Points in unit square and
triangles of small area. (Not finished yet.)
 Oct 30 (MT)

Finishing the proof from the last time. Variance, standard deviation,
covariance. Variance of a sum of random variables. Chebyshev's inequality.
Threshold functions. The function $1/n$ is a threshold function for triangle
containment.
 Nov 6 (MT)

Threshold function for containment of a balanced graph $H$. Lower bound for a
middle binomial coefficient. Chernoff inequality. Combinatorial discrepancy via
Chernoff.
 Nov 13 (RS)

Variants of Chernoff inequality, comparison to Central Limit Theorem.
Several easy applications.
Longer application to randomized rounding to solve a kmatching problem.
[MV 7.2]
 Nov 20 (RS)

Finishing the kmatching problem.
Randomized routing in a hypercube [MU 4.5.1].
 Nov 27 (MT)

Lovász local lemma, symmetric and general version. Proof skipped, only shown:
general implies symmetric. Two applications: edge disjoint paths and cycles of
length divisible by $k$ in directed graphs.
 Dec 4 (JSg)

Markov chains: definition, representation by finite automata and by matrices. Algorithms for 2SAT nad for 3SAT.
Markov chain on a finite path and on an infinite path.
 Dec 11 (RS)

More Markov chains: accesible/communicating states, states transient/recurrent, and null/positive recurrent, examples.
Periodic/aperiodic states/MC. Ergodic states/MC. Theorem about stationary distribution. Start of the proof.
 Dec 18 (RS)

Proof of the theorem about stationary distribution of Markov chains.
Motivation of the ballsandbins (birthday paradox).
 Jan 8 (RS)

Ballsandbins: upper and lower bound on the maxload.
Poisson random variables, Poisson approximation for ballsandbins.