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.

[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.