Martin Tancer
Lecture: Mon, 12:20, S8,
Exercise classes: Fri, 9:00, S8 (TA Tomáš Hons and Tung Ahn Vu).
Webpage for exercise classes is here.
List of topics covered by lectures is at the bottom of this webpage.
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 expected contents of the lecture,
you may check one of
the previous lectures
(some changes may occur).
Literature
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
Additional resources
-
[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).
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.
Slides from 2020
In case that you would find them useful, here are some slides from 2020 (not
for all lectures). However, they were intended for online teaching and it is
not guaranteed that they will match the lectures this year. Use on your own
risk: Lecture 1 , Lecture 2, Lecture 3, Lecture 4, Lecture 5, Lecture 6, Lecture 7.
Topics covered
- Sep 29
-
Motivation. Quick overview of basic notions in probability: probability space,
independence of events, conditional probability, union bound. Random
graph $G(n,p)$.
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. Satisfiability of CNF formulas. Erdős-Ko-Rado
theorem. (So far, an auxiliary lemma has been proved.)
[MV 1, 2.1, 2.3, AS 1.1, slides above (CNF formulas--lecture 2)]
- Oct 10 (Taught by Tung Anh Vu)
-
Finishing the proof Erdős-Ko-Rado theorem. Quick overview of random variables.
Expected number of fixed points in a random permutation. Szele's theorem
(Hamiltonian paths in tournaments.) Balancing unit vectors. MAXCUT. Sketch of
conditional expected value. [MV 1, 2.3, 3.1, 3.2, 3.3, AS 2.1]