Probabilistic Tools in Combinatorics

February 2023

Probabilistic Tools in Combinatorics

While the garden of probabilisitc methods grows so diverse in species, I tend to go in the other direction by restricting to the recurring themes. The notes selected, to my personal taste, some of the most elegant probabilistic proofs and organised them in a systematic way. I wrote five chapter in total:

  1. Probability and Counting. This chapter deals with bare-bone probability. Everything is done via partition, refinement and conditioning of the space, sometimes with the union bound. It might be the hardest chapter to master, but also a fascinating entry point for probabilistic thinking.
  2. Bounding Probability via Concentration. This chapter covers three concentration bounds. I selected less conventional examples to showcase the interpretation of concentration.
  3. Bounding Probability via Locality. This chapter introduces Lovász local lemma as a tool for lower bounding very small probability.
  4. Bounding Probability via Correlation. This chapter discusses the modeling of correlation and the famous FKG inequality, developing from its infant form (Chebyshev’s sum inequality) to a more powerful variant on product space.
  5. Expectation: Beyond Probability. The final chapter abandons the approaches pursued in previous ones. It explores something vastly different, namely using expectation as existential proofs. The power comes from its conjunction with the “alteration” idea which exploits linearity of expectation.

The notes also ship with two appendices that cover more involved results. I got my inspirations from lectures by Prof. Benny Sudakov and the book The Probabilistic Method by Alon and Spencer.

➤ PDF notes download

Return↩︎