R A N D O M R E G U L A R G R A P H S F A L L 2 0 1 8

**Lectures**: Tuesday, 11:00-12:50pm, in Warren Weaver Hall 1302.

** Lecturers**: Paul Bourgade, Eyal Lubetzky.

**Course description**:
The course will center around recent breakthroughs on sparse random regular graphs.

The first part will be devoted to the spectrum of such graphs, with three aspects:

(i) Bordenave's proof of Friedman's second eigenvalue theorem (arXiv:1502.04482);

(ii) Anantharaman's quantum ergodicity for deterministic regular graphs (arXiv:1512.06624)

(iii) Bauerschmidt, Huang and Yau's strong delocalization for uniform regular graphs of fixed degree (arXiv:1609.09052).

The second part will aim to go through the paper by Ding, Sly and Sun (arXiv:1310.4787) on maximal independent sets in random regular graphs, via belief propagation and tools from statistical physics.

**Prerequisites**: Basic knowledge of linear algebra and probability theory is required.

**Additional documents**:

For the first part of this course Anantharaman's ICM 2018 proceedings give some introduction to themes and results of interest.
For the second part of this course, see here for an introduction and related literature.

A tentative schedule for this course is (click on the title for detailed content):

- Sep. 11.
**Definitions, presentation of the results, organization.** - Sep. 18.
**Quantum ergodicity for deterministic graphs (after Anantharaman).** - Sep. 25.
**Edge Behavior I (by Eyal Lubetzky)** - Oct. 2.
**Edge Behavior II (by Yuval Peled)** - Oct. 9.
**No course, classes meet according to a Monday schedule** - Oct. 16.
**Edge Behavior III (by Yuval Peled), and Quantum unique ergodicity I (by Guillaume Dubach) for the uniform model** - Oct. 23.
**Quantum unique ergodicity II (by Guillaume Dubach) and Delocalization I, for the uniform model** - Oct. 30.
**Delocalization II, for the uniform model** - Nov. 6.
**Delocalization III, for the uniform model** - Nov. 13.
**Delocalization IV, for the uniform model** - Nov. 20.
**Anderson model (and generalizations) on d-regular graphs (by Christopher Thornett)** - Nov. 27.
**Quantum ergodicity on manifolds. Introduction to random constraint satisfaction problems (by Eyal Lubetzky)** - Dec. 4.
**Random constraint satisfaction problems I** - Dec. 11.
**Random constraint satisfaction problems II**