Content: Random discrete structures such as random graphs or matrices play a crucial role in discrete mathematics, because they enjoy properties that are difficult (or impossible) to obtain via deterministic constructions. For example, random structures are essential in the design of algorithms or error correcting codes. Furthermore, random discrete structures can be used to model a large variety of objects in physics, biology, or computer science (e.g., social networks). The goal of this course is to convey the most important models and the main analysis techniques, as well as a few instructive applications. Topics include

• fundamentals of discrete probability distributions,
• techniques for the analysis of rare events,
• random trees and graphs,
• applications in statistical mechanics,
• sampling and rapid mixing,
• applications in efficient decoding. The module is suitable for students of mathematics or discrete mathematics.

   

  Aims:

• To acquire knowledge of the basic phenomena that occur in random discrete structures.
• To gain competence in using basic techniques such as the first and second moment method.
• To understand large deviations phenomena.
• To be in a position to apply random structures in physics or computer science.

   

  Books:

  Alon, Spencer: The probabilistic method. Wiley 2000. Dembo, Montanari: Gibbs measures and phase transitions on sparse random graphs. Stanford 2009. Durrett: Random graph dynamics. Combridge 2007. Janson, Luczak, Rucinski: Random graphs. Wiley 2000.