Graduate Student Seminar - Jan Volec
听
Jan Volec will tell us about The Probabilistic Method and the Lovasz Local Lemma.
听
Abstract:
The Probabilistic Method is a powerful tool for tackling many problems that
appear in discrete mathematics, number theory, and computer science, and it has
experienced an impressive growth in the past 50 years. Roughly speaking, its
basic idea goes as follows: A way of proving existence of an object with
certain properties is to design an appropriate probability space, from which
a randomly drawn element has the desired properties with positive probability.
听
In the first part of the talk, we will give a gentle introduction to the
Probabilistic Method with an emphasis on its applications to some combinatorial
problems. Then, we focus on one of its most celebrated tools called Lovasz
Local Lemma, and, in the final part, we will drift to related algorithmic
questions. Using an ingenious recently discovered argument that is sometimes
described as "entropy compression", we present an algorithmic approach to the
Local Lemma that allows us to (almost) forget about the probability approach we
started with.听