The Lovász Local Lemma and its algorithmic version
(in Portuguese)
An exposition of the Lovász Local lemma, some
applications of the lemma in extremal combinatorics,
together with a proof of the Moser-Tardos algorithmic version.
An introduction to extremal combinatorics
(in Portuguese).
We introduce the use of the probabilistic method and the
polynomial method in extremal combinatorics
with the following examples:
the crossing number inequality,
graphs with large girth and large chromatic number,
Turán's theorem,
Sperner's theorem,
Frankl-Wilson theorem,
disproof of Borsuk's conjecture
and
the chromatic number of the R^n.