Dates: May 15, Fri, in class, plus to be decided.
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 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.
2. On any infinite transitive graph, SRW is at least diffusive. Lee-Peres (2009) Sections 1, 2, minus Subsection 2.1, plus try to solve Exercise 10.5 from my PGG notes. PGG Sections 10.1, 10.2 may contain explanations helping you understand the paper.
3. 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). Plus, solve one of the PGG Exercises 8.5, 8.6, 8.7.
4. Bottlenecks, burstiness, and fat tails regulate mixing times of non-Poissonian random walks. Paper by Delvenne, Lambiotte and Rocha (2013). There are probably some math details to fill in, but as an additional exercise, find the exact speed of convergence to stationarity on the complete graph with power-law waiting times with no cut-off. Plus, Proposition 7.9 from my PGG notes.
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.
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.29 using Wilson's algorithm.
8. 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.
9. Exchangability and the convergence of the Pólya urn using de Finetti's theorem. See this lecture by Yuval Peres. Prove Exercises 1 and 2 there, and generalize the warning example on page 2 by proving the following statement: if X_1,X_2,... is an exchangable sequence with E[X_i^2]<\infty, then E[X_iX_j]\geq 0; deduce that the members of an infinite exchangable sequence are pairwise positively correlated.
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.
11. Proof of the Harris-Kesten theorem p_c(\Z^2)=1/2 for bond percolation on the square grid, using the Russo-Seymour-Welsh inequality and Russo's formula. PGG notes Section 12.3, including solving Exercise 12.47. Can also try Exercise 12.48. See also Grimmett's book Sections 5.6, 5.8, in case you need more details.
12. Random-turn hex and other selection games: Peres-Schramm-Sheffield-Wilson paper in Amer Math Monthly.
13. The Totally Asymmetric Simple Exclusion Process and its hydrodynamic limit, Burgers' equation. See Marci Balázs's talk and my notes.
14. 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.
15. 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.