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.