Lectures: Wednesdays 15:30-18:00, room 301. Some extra make-up classes on Thursdays, 14:00-16:30, same location.
The final grade will be composed of 30% first HW set, 30% second HW set, 40% presentation.
Here is the first problem set. In principle due March 7, but we do not have a class that week, hence it is OK to hand it in later. You can ask me for help if you get stuck with something.
And here is the second problem set, due April 11, but let me know if you need more time.
Presentations: here is the list of topics. Probably April 11 Wed afternoon.
1.) Jan 17.
Stochastic domination, Strassen's theoerem, standard coupling in percolation. Phase transition for subgraph containment in Erdos-Renyi G(n,p). First and Second Moment Methods [PGG Section 12.3], [Alon-Spencer Section 4.4]. Component structure of G(n,(1+\eps)/n) for \eps < 0, \eps = 0, \eps > 0: stating the Erdos-Renyi-Luczak-Aldous results. [PGG Theorem 12.23]
2.) Jan 24.
Three proofs for the Galton-Watson phase transition [PGG Section 12.1]. Chung-Fuchs theorem on WLLN implying recurrence [Durrett's Probability Section 4.2], with the Cauchy non-example using 2-dim BM [PGG Exercise 12.8]. Sub-critical and critical cases for the Erdos-Renyi giant phase transition [PGG Theorem 12.23].
3.) Jan 31.
Proof in the supercritical case [PGG Theorem 12.23]. Poisson degree distribution [PGG Exercise 14.4]. Both are using the small variance Azuma Hoeffding [PGG Proposition 1.9]. The intuition why the connectivity threshold is at p \sim \log n / n [PGG Exercise 12.44].
Barabási-Albert preferential attachment graph, power law degree distribution, with ODE approximation and Azuma-Hoeffding. [Durrett's Random graph dynamics Section 4.1].
The notion of influences and pivotality, Russo-Margulis lemma [PGG equation (12.16)].
4.) Feb 7.
Introducing discrete Fourier analysis and randomized algorithms to understand threshold phenomena. Total (signed) influence is at most \sqrt{n}. Poincare inequality on the hypercube and its strengthening OSSS (2005). [Garban-Steif Sections IV.5 and XII.10]
5.) Feb 8.
Different revealment-type complexity measures for Boolean functions. Example 1: Critical percolation and random-turn hex. Example 2: iterated 3-Majority. The OS (2007) lower bound on revealment, and the application of OSSS05 and OS07 to Karp's conjecture [Garban Steif Thm VIII.8 and Section XII.10.].
Doob's h-transform for Markov-chains. Application: the discrete Bessel(3) process. [PGG Lemma 6.13] Another discrete approximation of a famous Stochastic Differential Equation: the projection of SRW on the hypercube onto the diagonal is the Ehrenfest urn model, or the discrete Ornstein-Uhlenbeck process.
6.) Feb 14.
Filling in the gap in the proof of OSSS. The general Poincare inequality for a Markov chain: Dirichlet variational formula for the spectral gap. Recalling what the spectral gap has to do with mixing times for random walks on finite graphs, and return probabilities for infinite graphs. [PGG Section 7.3]
Definition of isoperimetric profile, amenability, expander graphs. The difference between volume growth and isoperimetry: the lamplighter group. [PGG Section 5.1]
7.) Feb 21.
Stating the equivalences between spectral and isoperimetric expanders, and between von Neumann and Folner non-amenability and spectral radius<1. Very rough sketch of the proofs of the easier directions. [PGG Section 5.2, some bits from Sections 7.1-7.3] The harder directions will follow from the evolving set method.
For groups, fast volume growth implies relatively good isoperimetry (Coulhon-Saloff-Coste inequality). [PGG Section 5.3]
Evolving sets: statement and starting the proof. Will continue with Lemma 8.5. [PGG Chapter 8]
8.) Feb 28.
Finishing the proof for evolving sets. [PGG Chapter 8]
Liouville and strong Liouville property for recurrent chains and Z^d [PGG Section 9.2]
9.) March 14.
Equivalence of Liouville property, zero speed, zero asymptotic entropy, trivial Poisson-boundary. [PGG Chapter 9]
10.) March 21.
1/3 \leq p_c(\Z^2,bond) \leq 2/3. Peierl's method for finitely presented groups. Insertion and deletion tolerance, ergodicity. Burton-Keane argument. The Benjamini-Schramm conjectures. Brief glance into SLE. [PGG Sections 12.1 and 12.2]
11.) March 27.
Mass Transport Principle. BLPS characterization of amenability as hyperfiniteness. Kazhdan's property (T). FKG-Harris inequality. [PGG Sections 12.1 and 12.2]
12.) March 28.
RSW-technology, the Harris-Kesten theorem using OSSS. [PGG Section 12.3]
Ising, Potts, and FK Random Cluster models. Holley's proof of FKG. Existence of infinite volume measures. [PGG Section 13.1]
N. Alon, J. Spencer. The Probabilistic Method. 3rd edition. Wiley Interscience, 2008. Here is a copy.
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.
Christophe Garban, Jeff Steif. Noise sensitivity of Boolean functions and percolation. Cambridge University Press, 2014. http://math.univ-lyon1.fr/~garban/Fichiers/book.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. Cambridge University Press, 2017. 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 and Yuval Peres. Probability on trees and networks. Cambridge University Press, 2016. http://mypage.iu.edu/%7Erdlyons/prbtree/prbtree.html
Gábor Pete. Probability and geometry on groups. Book in preparation. PGG.pdf