Combinatória Probabilística

In this advanced-level course we will study some advanced applications of probabilistic methods in combinatorics and combinatorial number theory, including:

• The Erdös–Rényi random graph (chromatic number, threshold for spanning subgraphs).
• The Lovász Local Lemma, and applications.
• Dependent random choice, and applications in extremal graph theory, Ramsey theory, and additive combinatorics.
• Applications of quasirandomness in Ramsey theory.
• Martingales and concentration inequalities.
• Random graph processes (the Rödl nibble, the differential equations method), and applications to number theory.
• Discrepancy (six standard deviations suffice, the Beck–Fiala theorem).
• The method of hypergraph containers, and applications to random graphs.

Referências:
[1] N. Alon and J.H. Spencer, The Probabilistic Method, 4th edition, Wiley, New York, 2016.
[2] J. Balogh, R. Morris and W. Samotij, The method of hypergraph containers, Proc. Int. Cong. Math., Rio de Janeiro, 2018, Vol. 3, 3045–3078.
[3] D. Conlon, J. Fox and B. Sudakov, Recent developments in graph Ramsey theory, Surveys in Combinatorics, Cambridge University Press, 2015.
[4] J. Fox and B. Sudakov, Dependent random choice, Random Structures Algorithms, 38 (2011), 1–32.

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