Dates: May 17, Fri, from 12:15 am to 15:45 pm.
Keep the talks simple, and don't try to cover everything that you have read about; rather, give just enough background and motiviation that makes it possible to appreciate your topic, and prove at least one non-trivial statement. (Could be just an interesting lemma that is important in the proof of the main theorem, but then you should have some idea about the outline of the entire proof.) Make sure you understand every single sentence you are saying. Using PDF slides is more than recommended, due to the time constraints. I will help with the reading or the extra HW problem(s) if you come and ask. If there is no HW problem assigned to a topic, then I feel that understanding the topic is enough work in itself.
1. The speed of random walks on the lamplighter groups from Section 9.1 of my PGG notes. Solve two exercises from Exercises 9.1-9.3.
2. The Liouville and strong Liouville property of harmonic functions on transitive graphs. Give an account of some of Section 9.2 of my PGG notes, and solve two exercises from there.
3. The Alon-Milman or Jerrum-Sinclair theorem connecting the isoperimetric constant to the spectral gap on a finite graph. Section 13.3 in the Levin-Peres-Wilmer book from our main reading list, or Section 1.2 of this Davidoff-Sarnak-Valette book. If you use the second book, make sure you can at least state a version for non-regular graphs and reversible Markov chains. Plus, solve PGG Exercise 7.18 or 7.19.
4. The evolving sets method to deduce heat kernel decay or mixing from the isoperimetric profile. Here is the original Morris-Peres paper (2003), but my PGG notes Sections 8.2 and 8.3 contain more explanations (with some details missing). You can concentrate on the non-amenable case, if you want. Plus, solve one of the PGG Exercises 8.5, 8.6, 8.7.
5. The Benjamini-Schramm limit of bounded degree finite planar graphs is always recurrent. This is the original Benjamini-Schramm paper (2000) where they introduced this limit notion. The beautiful proof uses circle packings. Plus, solve PGG Exercise 14.1 or 14.15.
6. The Trotter-Virág proof of Wigner's semicircle law for the limiting eigenvalue distribution of large random symmetric Gaussian matrices (the GOE ensemble), using Benjamini-Schramm convergence of graphs. Watch Virág's ICM 2014 talk up to time 21:16, and fill in the details.
7. David Wilson's algorithm to generate the uniform random spanning tree (UST) using loop-erased random walks (LERW). You may concentrate on the unweighted case. Lyons-Peres book Section 4.1, plus solve PGG Exercise 11.3 or 11.4.
8. Something about the Abelian sandpile model. For an introduction, see Wikipedia page, and/or this AMS Notices article. And here is a survey by Antal Járai. If you are interested in the topic, I'll figure out the exact task.
9. Azuma-Hoeffding large deviations for martingales, and the concentration of the chromatic number of the Erdős-Rényi graph G(n,1/2). See my PGG notes, Sections 1.2 and 6.3, and/or Alon-Spencer book Sections 7.1-7.3. Plus, solve PGG Exercises 1.9 and 1.13.
10. The independence ratio of the random 3-regular graph is bounded away from 1/2, despite being locally a tree, proved in this paper of Bollobás (1981). Plus, prove PGG Exercise 14.4 or 14.8.
11. The statement of the Szemerédi Regularity Lemma, and its application to testing triangle-freeness and to the simplest case of Szemerédi's Abel-prize winning theorem (proved first by Roth, 1953): every positive density subset of the integers contains a 3-term arithmetic progression. See the Alon-Spencer book Section 17.4, then Section 17.6, Exercise 3, and the Tao-Vu book Section 10.6.
12. The Harris-FKG inequality and Zhang's proof of Harris' theorem p_c(Z^2) \geq 1/2 for bond percolation on the square grid; see PGG notes Theorems 12.3, 13.1, 12.28. Solve Exercise 12.58 regarding the IIC. See also Grimmett's book Sections 5.6, 5.8, in case you need more details.
13. Present Hutchcroft's result that percolation on transitive graphs of exponential growth have no infinite cluster at p_c. Plus, as an exercise, combine some Z^d and some infinite tree into one connected graph so that it has one infinite cluster at some p, but infinitely many clusters at some q>p, a behaviour that transitive graphs cannot have.
14. In Bálint Tóth's corner percolation model, there are no infinite paths, as proved in Section 2 of this paper of mine. As an exercise, show the same in the trixor model, no infinite clusters, as mentioned in Section 7.
15. Random-turn hex and other selection games: Peres-Schramm-Sheffield-Wilson paper in Amer Math Monthly.
16. The Totally Asymmetric Simple Exclusion Process and its hydrodynamic limit, Burgers' equation. See Marci Balázs's talk and my notes.