Coronavirus (Covid-19): Latest updates and information
Skip to main content Skip to navigation

MA952 - The Probabilistic Method

Lecturer: Dr András Máthé

Term(s): Term 2

Commitment: 30 lectures

Assessment: Oral exam

Prerequisites: An undergraduate introductory probability module and a combinatorics module should be enough to follow most lectures; knowledge of measure theory and advanced probability (covering martingales) can be helpful but not essential.

Content:

The probabilistic method is the way of proving that a certain mathematical object with desired properties exists --- by showing that a random choice of an object (in a suitable class) has the desired property with positive probability. This method is primarily used to construct combinatorial objects. The lectures will present various probabilistic methods through applications mainly in combinatorics but also in other areas of mathematics. We will cover selected chapters from the Alon--Spencer book of the same title. Topics will include

  • First moment method
  • Second moment method
  • Lovász local lemma
  • Correlation inequalities
  • Martingales
  • Janson inequalities
  • Applications in geometry (discrepancy).

References:

Noga Alon – Joel H Spencer: The Probabilistic Method, Wiley (3rd edition)