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.