Dates: May 19, Fri, from 10 am to 2 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.
Remember that you may suggest project topics yourselves.
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. [Alexander Bíró and Luca Pusztaházi]
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.
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 much more explanation (with some details missing). You can concentrate on the non-amenable case. 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, in case you didn't do it from the First Problem Set.
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). Lyons-Peres book Section 4.1, plus Exercise 4.28 using Wilson's algorithm.
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. Proof of the power-law degree distribution for the Barabási-Albert preferential attachment models, following Section 4.1 of Durrett's RGD book. Investigate what changes if, in the "master equation" for N(k+1,t)-N(k,t), we do not ignore the possibility of multiple edges. [Dani Oláh and Zsófi Talyigás]
10. The concentration of the chromatic number of the Erdős-Rényi graph G(n,1/2), around the value 2\log_2 n, using martingale concentration, due to Béla Bollobás (1988). The main source is the Alon-Spencer book Sections 4.5, 7.3, 10.3. [Noémi Horváth and Gergely Vastag]
11. The statement and proof of the Lovász Local Lemma, and its application to the Ramsey number lower bound R(3,k) > c k^2 / \log^2 k, from the Alon-Spencer book Sections 5.1 and 5.3. [Máté Baranyi and Dani Prokaj]
12. Triangle-free graphs have large independence numbers, and the Ramsey number upper bound R(3,k) < C k^2 / \log k by Ajtai, Komlós and Szemerédi (1980), following the simple proof by Shearer and Alon, as presented in the Alon-Spencer book, the Probabilistic Lens in Appendix A, pages 321-322.
13. 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).
14. 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.
15. 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.49 regarding the IIC. See also Grimmett's book Sections 5.6, 5.8, in case you need more details.
16. 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.
17. 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.
18. Random-turn hex and other selection games: Peres-Schramm-Sheffield-Wilson paper in Amer Math Monthly. [Gabor Varga]
19. The Totally Asymmetric Simple Exclusion Process and its hydrodynamic limit, Burgers' equation. See Marci Balázs's talk and my notes. [Marcell Nagy and Katinka Páll]
20. Read Chapter 6 of the Gács-Lovász Complexity Theory lecture notes on randomized algorithms, present some of it, plus solve two exercises from the end of that chapter. [Richárd Kusicza]
21. One-way functions and pseudorandom generators are in the heart of most modern cryptosystems (see also http://en.wikipedia.org/wiki/One-way_function). However, the existence of neither has been proved; this is a major open problem in computer science and cryptography. It turns out that their existences are equivalent to each other: you can construct one from the other. You will need a little bit of probability and complexity theory. Chapter 8 of the Gács-Lovász lecture notes is a nice source for this project; additional sources could be any of the books by Oded Goldreich, for instance, this introductory one. [Lóránt Nagy]