SoSe 16: The Probabilistic Method
Tibor Szabo
Hinweise für Studierende
Kommentar
Abstract: 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-2016/.
SchließenLiteraturhinweise
Suggested reading: “N. Alon, J. Spencer: The Probabilistic Method
14 Termine
Regelmäßige Termine der Lehrveranstaltung