Tópicos em Combinatória Probabilística

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

  • The Erd˝os–R´enyi random graph (concentration of the chromatic number, proof of the Kahn–Kalai conjecture, applications of quasirandomness and absorption).
  • The Lov´asz Local Lemma, and applications to Ramsey theory and discrepancy.
  • Dependent random choice, and applications to Ramsey theory.
  • Martingales and concentration inequalities.
  • Random graph processes (the R¨odl nibble, the differential equations method).
  • The method of hypergraph containers, and applications to random graphs.

References
[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] F. Botler, M. Collares, T. Martins, W. Mendon¸ca, R. Morris and G. Mota, Combinat´oria, XXXIII Col´oquio Brasileiro de Matem´atica (SBM/IMPA).
[4] D. Conlon, J. Fox and B. Sudakov, Recent developments in graph Ramsey theory, Surveys in Combinatorics, Cambridge University Press, 2015.
[5] J. Fox and B. Sudakov, Dependent random choice, Random Structures Algorithms, 38 (2011), 1–32.