Dates: June 1 in class and ..?..
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; solos or triples are also possible.) Aim for a presentation of 2*8 minutes, preferably with pdf slides. 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.) Most importantly: 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 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.
1. A very simple model of virus spreading: two phase transitions for branching random walk on regular trees, by Madras and Schinazi (1992). If you are really curious, can also check out the harder case of the contact process, e.g., this paper by Stacey (1996) and the references there.
2. The Liouville property of harmonic functions, from Section 9.2 of my PGG notes: \Z^d for any d and the lamplighter graphs \Z_2 \wr \Z^d with d=1,2 are Liouville, while \Z_2 \wr \Z^d with d \ge 3 are not Liouville. Also, solve Exercise 9.7 from that section.
3. Bottlenecks, burstiness, and fat tails regulate mixing times of non-Poissonian random walks. Paper by Delvenne, Lambiotte and Rocha (2013). The main difficulty is to decide what is done mathematically rigorously, what is not, and filling in as many math details as you can.
4. The method of (Strong) Stationary Stopping Times to give upper bounds on the mixing time of Markov chains, from this Aldous-Diaconis (1986) Amer Math Monthly paper. Also, be aware that strong stationary stopping times always exist, by Proposition 3.2 of this Aldous-Diaconis (1987) paper.
5. 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.
6. 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.
7. 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).
8. 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.
9. 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.
10. Refresh your memory about the Azuma-Hoeffding large deviations for martingales, and, as an application, show 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. As further applications, solve PGG Exercises 6.12 and 6.13.
11. Proof of the power-law degree distribution for the Barabási-Albert preferential attachment models, following Section 4.1 of Durrett's RGD book, using Azuma-Hoeffding. 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.
12. 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).
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. 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 (to be slightly updated, e.g., by adding references, soon).
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.