SoSe 20: The Probabilistic Method
Tibor Szabo
Comments
The probabilistic method is a surprisingly effective technique in many areas of discrete mathematics, often giving solutions to purely deterministic problems where one would not expect randomness to play a role. The basic premise is as follows: in order to show the existence of a structure with certain properties, we first construct an appropriate probability space, and then show that a randomly chosen element has the desired properties with positive probability.
Following the remarkable success of its applications, this field has seen tremendous growth in recent decades. In this course we will get to know the probabilistic method, introducing its various tools and through some delightful applications. The topics we shall cover include:
- linearity of expectation and the method of alterations
- the second moment method
- the Lovász Local Lemma
- correlation inequalities
- martingales and large deviation inequalities
- Janson's inequality and the Poisson paradigm.
For further information, see
http://discretemath.imp.fu-berlin.de/DMIII-2020/.”
close
Suggested reading
Main text: N. Alon, J. Spencer: The Probabilistic Method (Fourth edition, Wiley, 2016)
Further reading: B. Bollobas, Random Graphs, (Second Edition, Cambridge University Press, 2001)
S. Janson, T. Luczak and A. Rucinski, Random Graphs, (Wiley, 2000)
M. Molloy and B. Reed, Graph Colouring and the Probabilistic Method, (Springer, 2002)
14 Class schedule
Additional appointments
Thu, 2020-07-23 14:00 - 15:00Regular appointments
Location:
A6/SR 025/026 Seminarraum (Arnimallee 6)