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.
• Proof of the Kesten-McKay law by the method of moments, remark that the generating function to solve the tree-induction is nothing but the Stieltjes transform.
  Statement of the result in Bauerschmidt-Huang-Yau (local law) and consequences (isotropic delocalization, quantum unique ergodicity).
  Statement of the result in Anatharaman (quantum ergodicity for determinisitc graphs, only assuming Benjamini-Schramm convergence and spectral gap).
• Sep. 18. Quantum ergodicity for deterministic graphs (after Anantharaman).
• First proof from arXiv:1512.06624 explained.
• Sep. 25. Edge Behavior I (by Eyal Lubetzky)
• Cheeger's inequality, existence of non-trivial spectral gaps, Alon-Boppana bound, non-backtracking random walk and its mixing time, locally tree-like structure for the configuration model.
• Oct. 2. Edge Behavior II (by Yuval Peled)
• Start of the proof of extreme non-trivial eigenvalues sticking to the bulk (Friedmann's theorem) by Bordenave, arXiv:1502.04482. Non-backtracking operator, Ihara-Bass formula.
• 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
• Edge Behavior III: moment of the non-backtracking matrix, recentering and reduction to tangle free paths. Counting.
  Quantum unique ergodicity I: from delocalization to isotropic delocalization and QUE, assuming the exchangeability lemma.
• Oct. 23. Quantum unique ergodicity II (by Guillaume Dubach) and Delocalization I, for the uniform model
• Quantum unique ergodicity II: the exchangeability lemma, elde and vertex colorings of graphs generaed by partitions, conclusion.
  Delocalization I: tree extension of balls in d-regular graphs, main theorem on approximation of the Green's function.
• Oct. 30. Delocalization II, for the uniform model
• Random walk heuristics for the Green's function, renormalization problem.
  Green' function of the tree extension: bounds on the excess in balls, bounds of non-bracktracking walks in terms of excess, Green's function of graph and its relation to Green's function of its cover, size order of the Green' function of the tree extension.
  Consequences: local law, delocalization.
• Nov. 6. Delocalization III, for the uniform model
• Start of the proof for the approximtion with tree extensions: resolvent expansions, graph switchings on balls' boundary, induction on scales.
• Nov. 13. Delocalization IV, for the uniform model
• End of the proof for the approximtion with tree extensions: concentration.
• Nov. 20. Anderson model (and generalizations) on d-regular graphs (by Christopher Thornett)
• From a paper by after Anantharaman-Sabri.
• Nov. 27. Quantum ergodicity on manifolds. Introduction to random constraint satisfaction problems (by Eyal Lubetzky)
• tba
• Dec. 4. Random constraint satisfaction problems I
• By Eyal Lubetzky, after Ding-Sly-Sun.
• Dec. 11. Random constraint satisfaction problems II
• By Eyal Lubetzky, after Ding-Sly-Sun.