# MA3H4 Random Discrete Structures

Not Running in 2015/16

Lecturer:

Term(s):

Status for Mathematics students: List A

Commitment: 30 lectures

Assessment: 3 hour exam 85%, assigned exercises 15%

Prerequisites: MA132 Foundations or PH126 Starting Formal Logic. Some exposure to at least one of MA222 Metric Spaces, MA359 Measure Theory or PH210 Symbolic Logic is also recommended

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.

Year 1 regs and modules
G100 G103 GL11 G1NC

Year 2 regs and modules
G100 G103 GL11 G1NC

Year 3 regs and modules
G100 G103

Year 4 regs and modules
G103

Past Exams
Core module averages