O Método Probabilístico

In this  advanced-level course we will study selected topics from the book “The Probabilistic Method” by Noga Alon and Joel Spencer [1], for example:

• The Erdös–Rényi random graph (emergence of the giant component,  chromatic number, threshold for Hamilton cycles, and other spanning  subgraphs).
• Concentration inequalities (the inequalities of Chernoff, Azuma–Hoeffding,  Janson, Suen, Talagrand, Rödl–Rucinski, Kim–Vu).
• Random graph processes (the Rödl nibble, the differential equations  method, applications to the triangle-free and triangle-removal  processes).
• The Lovász Local Lemma, and applications to Ramsey theory.
• Discrepancy (six standard deviations suffice, the Beck–Fiala theorem).
• Dependent random choice, and applications in extremal graph theory,  Ramsey theory, and additive combinatorics.
• Quasi-random graphs, and Szemerédi’s regularity lemma.
• The method of hypergraph containers, and applications to random  graphs.

Referencia:
[1] N. Alon and J.  H. Spencer, The Probabilistic Method,  4th  edition,  Wiley, NewYork, 2016.

* Ementa básica. O professor tem autonomia para efetuar qualquer alteração.