## 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).
### Grading

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.

## Schedule

**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