MAT 589 Topics in Probability, Statistics and Dynamics - Stochastic processes on graphs (Spring 2018)

Instructor Allan Sly (asly@princeton)

Class time 1:30-2:50 on Mondays and Wednesdays at 120 Lewis Library.

Office hours
Wednesday 11:00-12:00 or by arrangement. Room 405 Fine Hall.

The first half of the course will begin with the classical results about random graphs, their properties and phase transitions such as connectivity, component size and local structure. We will then examine a range of stochastic processes on these networks including spin systems, the contact process, SIS model, voter model and various models of the diffusion of information on networks. Then for the second half of the course we will focus on random constraint satisfaction problems, models like random colourings or max-cut on random graphs and random k-sat. These models exhibit a range of phase transitions described by statistical physics and we will examine the state of the art methods that have established to prove some of these predictions.

The target audience is PhD students both from mathematics and other departments (e.g. PACM, ORFE, CS, EE). The beginning of the course will cover some of the fundamentals of random graphs while the later topics, particularly on random CSPs will be more specialized.

I will try to emphasize the big picture and heuristics on the one hand while also giving the tools to give rigorous proofs (but not always in their full detail).


If you need to receive a grade for the course, there will be three problem sets over the semester. Even if you don't need a grade you are encouraged to try the problems. There will be no final exam.

Reference material

I will be writing lecture notes for some of the course, particularly the latter sections on random CSPs and will supplement it with links to other sets of notes. I will also upload my handwritten notes which I use for class. Some good references to models of random graphs are available online here.


Feb 5: Introduction. Erdos Renyi random graphs, cycles Notes
Feb 7: Configuration model. Local weak limits. Notes
Feb 12: Component sizes. Notes
Feb 14: Component sizes - critical case.
Feb 19: Distances and Diameter. Notes
Feb 21: Distances and Diameter continued.
Feb 26: Random walks on random graphs. Notes Additional references: Markov chain text Markov Chains and Mixing Times. Papers [FR08] [LS10] [DLP14] [BLPS17]
Feb 28: Random walks on random graphs.
Mar 5: Infection models (SIR and contact Process). Notes
Mar 7: Infection models: SIR
Mar 12: Infection models: Contact Process - trees. Additional reference: [Pemantle92] [LS15]
Mar 14: Infection models: Contact Process - random graphs.

Spring Break

Latexed lecture notes for second half of the course on spin systems on random graphs and random CSPs Pdf

Mar 26: Spin systems and phase transitions Notes
Mar 28: Spin systems and phase transitions Notes
Apr 2: Spin systems on trees Notes
Apr 4: Reconstruction problem on trees
Apr 9: Ising Model on random Graphs Notes
Apr 11: Moments of the Partition Function Notes
Apr 16: Moments of the Partition Function
Apr 18: The hardcore model and Independent sets Notes
Apr 23: The hardcore model and Independent sets
Apr 25: The hardcore model and Independent sets
Apr 30: Predictions in Statistical Physics
May 2: Interpolation Methods Notes

Problem Sets

Problem set: Notes