Lectures: Fridays 12:15-14:00, room H45a
Email: my first name at math dot bme dot hu
Office hours: see here.
Course poster: this.
Here is the first set of homework problems, due April 7. Here is the second set, due May 15. It is OK to think about the problems together, you can also ask me for help, but the solutions should be written up individually. Mindless copying will be frowned upon.
There will also be final projects, to be worked out in pairs. This will consist of reading and understanding a research article or book section, giving a 15 + 15 minutes presentation by the two of you, and solving one or two extra homework problems related to the presentation. Here is the list of topics. You can also suggest topics that you would like to learn about. The proposed time for the presentations is May 19, Friday, 10 am - 2 pm.
The weights for the final grade will be 30% first HW, 30% second HW, 40% presentation.
The grading scheme is that 2 from 48%, 3 from 60%, 4 from 72%, 5 from 84%.
1.) Feb. 10. Pólya's theorem on the recurrence and transience of SRW on \Z^d, using the Azuma-Hoeffding large deviation inequality. Remark: martingle difference satisfy the conditions of Azuma-Hoeffding.
2.) Feb. 17. Proving the Azuma-Hoeffding large deviation inequality. Existence of large deviations rate function using subadditivity (Fekete's lemma). Computing the exponential rate of decay of the return probabilities on the d-regular tree T_d.
3.) Feb. 24. Definition of d-dimensional isoperimetry and amenability. The difference between non-amenability and exponential growth: the lamplighter Cayley graphs. Stating the Varopoulos (1985) and Kesten-Cheeger-Dodziuk-Mohar (1959-1988) theorems on return probabilities.
4.) March 3. Markov operator, reversibility and self-adjointness. The notion of spectral radius and operator norm. The intuition behind the Kesten-Cheeger theorem.
5.) March 10. The spectrum of finite reversible Markov chains. Examples: cycle and hypercube. Bounding the uniform distance from stationarity using the absolute spectral gap.
6.) March 17. L^p and total variation mixing. O(n\log n) bound for the hypercube, using the coupon collector problem. Isoperimetric and spectral definitions of (n,d,c) expander graphs, stating the Alon-Milman theorem.
7.) March 24. Pinsker's random d-regular bipartite graph is an expander with high probability. The evolution of the Erdos-Renyi random graph G(n,p): stochastic domination, first and second moment method for the phase transition of containing a triangle.
8.) March 31. Finishing the Pinsker proof. Component structure of G(n,(1+\eps)/n) for \eps < 0, \eps = 0, \eps > 0: stating the Erdos-Renyi-Luczak-Aldous results. Starting the proof: stochastic domination of the cluster of a fixed vertex by a Poisson Galton-Watson tree, using an exploration process. Understanding the phase transition between the extiction and survival of GW trees, using the exploration RW.
9.) April 7. The critical case: arguing that P[surviving for > n steps] \asymp P[getting to height > \sqrt{n} in the RW] \asymp 1/\sqrt{n}. The notion of size-biasing. A supercritical GW tree conditioned to die out is a sub-critical GW tree. Doob transform of Markov chains; example: SRW on \Z conditioned to stay positive forever, the "discrete Bessel(3) process".
10.) April 21. Finishing the G(n,p) cluster structure given the GW results. The intuition why the connectivity threshold is at p \sim \log n / n. Concentration of chromatic number of G(n,p) using Azuma-Hoeffding.
11.) April 28. Barabási-Albert preferential attachment graph. Physics ODE argument for power law degree distribution. de Finetti's theorem for exchangable random sequences, and convergence in Pólya's urn. Starting percolation theory: the notion of p_c, Kolmogorov's 01 law, the example of regular trees.
12.) May 5. Peierls contour method for percolation on Z^2. Number of infinite clusters: ergodocity and the Burton-Keane argument for amenable transitive graphs. Stating the general Benjamini-Schramm conjectures, and the known results.
13.) May 12. (plan) Explaining a little bit the Harris-Kesten theorem for critical percolation on planar lattices, and Smirnov's theorem on the conformal invariance, with the universality conjecture. FK random cluster and Ising and Potts models. The existence of infinite volume limits, using the FKG inequality.
Rick Durrett. Probability: theory and examples. 4th edition. Cambridge University Press, 2010. https://www.math.duke.edu/~rtd/PTE/PTE4_1.pdf.
Rick Durrett. Random graph dynamics. Cambridge University Press, 2007. https://www.math.duke.edu/~rtd/RGD/RGD.pdf.
Geoffrey Grimmett. Probability on graphs. Cambridge University Press, 2010. http://www.statslab.cam.ac.uk/~grg/books/pgs.html.
Remco van der Hofstad. Random graphs and complex networks, Vol. I. Book in preparation, http://www.win.tue.nl/~rhofstad/NotesRGCN.pdf
David Levin, Yuval Peres, Elizabeth Wilmer. Markov chains and mixing times. American Mathematical Society, 2008. http://pages.uoregon.edu/dlevin/MARKOV/.
Russ Lyons with Yuval Peres. Probability on trees and networks. Book in preparation, to appear at Cambridge University Press. http://mypage.iu.edu/%7Erdlyons/prbtree/prbtree.html
Gábor Pete. Probability and geometry on groups. Book in preparation. PGG.pdf