Dates: May 14, during class, and maybe something else? ... to be decided
Form pairs, choose a topic from the list below, and tell me your choice --- first come, first served. (If you cannot find a pair, let me know; in exceptional cases, solos or triples are also possible.) Aim for a presentation of 2*8 minutes, on Teams. That's probably around 8 PDF slides altogether, at most 12. Make at least one practice run before your actual presentation, so that you see the timing. The pair will get a joint mark, hence you are as responsible for your partner as for yourself. Keep the talks simple, don't try to cover everything that you have read about; rather, give just enough background and motivation 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: if I get suspicious, I will ask during the talk, and you will lose points if you cannot answer. (The audience is also encouraged to interrupt with questions. I think these are really cool topics --- we want to understand something about them.) If you are not sure what to cover exactly in the talk, feel free to ask. Also, I will help with the reading or the extra exercises if you come and ask. Write down and hand in the solutions of your extra exercises by noon of the day before your presentation.
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. [József Kiss and Viktor Körtvélyesi]
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. How to use random walks to compute the volume of a convex body. The first section from Chapter 6 of this Lovász survey. Fill in missing details, such as the formula for the average waiting time, the last display on page 36.
6. From Section 16.1 of the Levin-Peres-Wilmer book, present the coupling upper bound and the Wilson lower bound for the mixing time of adjacent transpositions. Solve the exercises referenced during the proofs.
7. 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 (as on the picture to the right). Plus, solve PGG Exercise 14.1 or 14.15.
8. 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 (the actual proof starts at 7:30, in case you get confused by the intro).
9. 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.
10. Something about the Abelian sandpile model, shown on this picture to the left. 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.
11. 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, present the Gaussian wave construction of density 0.4298 from Csóka-Gerencsér-Harangi-Virág (2015). More precisely: the statement and proof of Thm 3, the statement of Thm 4, and the first approach in the proof of Thm 1 (page 11). Additional exercise: find a small mistake in the statement of Thm 3 --- it claims something that is not actually proved (it is not even true, but you don't have to prove that).
12. 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.
13. 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.
14. 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.
15. In Bálint Tóth's corner percolation model (shown on the picture to the left), 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.
16. Random-turn hex and other selection games: Peres-Schramm-Sheffield-Wilson paper in Amer Math Monthly. About the exact task, please contact me.
17. The Totally Asymmetric Simple Exclusion Process and its hydrodynamic limit, Burgers' equation. See Marci Balázs's talk and my notes.
18. 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.