## MAT 1045HF PROBABILITY AND GEOMETRY ON GROUPS FALL 2009

Gábor Pete

Email: gabor @ as you would guess from this homepage address.
Downtown office: ES 4146 (on the South wall of the Earth Sciences building, towards West)

Lectures: Wednesdays 1-4 pm, Room BA 3000

Grading: Exercise solutions totaling 8 pts (each exercise is worth 2^{number of its stars}) and 2 lecture write-ups (twice 2 pts) are to be submitted.

Lecture notes: The notes will appear here first more-or-less in their original forms as written up by the students, only slightly improved. In particular, I don't promise that there are no mistakes left. As time goes on, I will merge and revise them.

HERE IS THE CURRENT VERSION. (Oct 22, 2013.) 218 pages. This seems to be turning into a book.

• Lecture 1: Basic random walk examples: Z^d and T_k. Recurrence, transience, Green's function, spectral radius. Basic group theory definitions: free groups and presentations, Cayley graphs. [Ben and Kyle]
• Lecture 2, plus a bit from Lecture 3: A Large Deviation inequality (Azuma-Hoeffding). Main theorems on free groups (Nielsen-Schreier and Schreier Index Formula), with topological proofs: fundamental groups and covering spaces. Ping-pong lemma, free subgroups of SL_2(Z). Topological meaning of a presentation, Rips complex. [Andrew and Lluis and Gabor]
• Middle of Lecture 3: Definition and examples of quasi-isometries. Q-isom invariance of volume growth, finitely presentedness, number of ends. The "Fundamental Observation of Geometric Group Theory". Corollary: Any finite index subgroup of a finitely generated group is finitely generated. [Kostya]
• End of Lecture 3, plus Lecture 4: Definition and basic properties of nilpotent and solvable groups and of semi-direct products. The Heisenberg group. The main ideas of the proof of the Milnor-Wolf theorem: a finitely generated infinite solvable group either has exponential growth, or it is almost nilpotent, hence has polynomial growth. [Siyu and Ben and Gabor]
• Lecture 5: Expanding homomorphisms of nilpotent groups, and a glance into intermediate growth. Isoperimetric inequalities, (non-)amenability, paradoxical decompositions, invariant means, Folner and von Neumann. Isoperimetry versus volume growth: the lamplighter group. [Eric and Jeremy]
• Lecture 6: Discrete potential theory: the gradient, its adjoint, the Laplacian, harmonic functions, flows, Dirichlet energy. Terry Lyons's flow description of transience. Quasi-isometry invariance of transience/recurrence. Proving that ||P|| equals \lim_n p_n(x,x)^{1/n}. [Andrew and Jim]
• Lecture 7: Proof of the Kesten-Cheeger-Dodziuk-Mohar characterization of non-amenability by spectral radius. Dirichlet and Sobolev inequalities. Finite version: expanders (Alon-Milman). Large spectral gap implies fast convergence to stationarity. Simple examples. Stating the Nash inequalities. [Eric and Jeremy]
• Lecture 8-9: Poincaré inequalities. Evolving sets: from isoperimetric profile to return probabilities, even in the non-reversible case. Martingales. (Most of Lecture 8 is cancelled due to Elliot Lieb's lecture on entropy.) [Kyle and Lluis]
• Lecture 10: Speed and entropy of random walks, the Liouville property (no non-trivial bounded harmonic functions), Lévy's zero-one law. Examples: Z^d, regular tree, and the lamplighter groups. [Siyu and Jim]
• Lecture 11: Equivalence between positive entropy and positive speed. Equivalence between non-Liouville and non-triviality of the Poisson boundary. High-level sketch of Kleiner's proof of Gromov's polynomial growth theorem, using that 1. the linear space of Lipschitz harmonic functions on a polynomial growth group is finite dimensional, and 2. any amenable group has a non-constant equivariant harmonic embedding into Hilbert space. Mentioning Thompson's group F and the Basilica group. (Shorter lecture due to Grad Student Seminar on constructing Almost Invariant sequences in amenable topological groups.) [Kostya and Gabor]
• Lecture 12, plus a few extra sections: An advertisement for several things we didn't have time for, with a lot of exercises. Rate of escape of random walks. Kazhdan's property (T). Harmonic Dirichlet functions. Free and Wired Uniform Spanning Forests. Percolation on infinite and finite groups. Random walks on percolation clusters. Bootstrap percolation. Local approximation of infinite groups. Quasi-isometric rigidity. [Eric and Lluis and Gabor]

Here is the LaTeX template for the lecture write-ups, and here is the compiled pdf. (Revised on Oct 23!) Looking at these two files will reveal a few technical details, like how to write conditional probabilities, or how to refer to lemmas and equations. Please note that the two of you are equally responsible for the entire file you submit to me, so you both should agree with everything, and help each other with both math and LaTeX.

Summary: Probability is one of the fastest developing areas of mathematics today, finding new connections to other branches constantly. One example is the rich interplay between large-scale geometric properties of a space and the behaviour of stochastic processes (like random walks and percolation) on the space. The obvious best source of discrete metric spaces are the Cayley graphs of finitely generated groups, especially that their large-scale geometric (and hence, probabilistic) properties reflect the algebraic properties. A famous example is the construction of expander graphs using group representations, another one is Gromov's theorem on the equivalence between a group being almost nilpotent and the polynomial volume growth of its Cayley graphs. The course will contain a large variety of interrelated topics in this area, with an emphasis on open problems.

A tentative non-exhaustive list of topics: Recurrence, transience, spectral radius of random walks. Free groups, presentations, nilpotent and solvable groups. Volume growth versus isoperimetric inequalities. Proof of sharp d-dim isoperimetry in Z^d using entropy inequalities. Random walk characterization of d-dim isoperimetry, using evolving sets (Morris-Peres 2003), and of non-amenability (Kesten 1959, Cheeger 1970, etc). Paradoxical decompositions and non-amenability. Expander constructions using Kazhdan's T and the zig-zag product. Expanders and sum-product phenomena. Entropy and speed of random walks and boundaries of groups. Gromov-hyperbolic groups. Kleiner's proof (2007) of Gromov's theorem (1980): polynomial volume growth means almost nilpotent. Grigorchuk's group (1984) with superpolynomial but subexponential growth. Fractal groups. Percolation in the plane: the Harris-Kesten theorem on p_c=1/2, introduction to conformal invariance. Percolation on Z^d, renormalization in supercritical percolation. Benjamini-Lyons-Peres-Schramm (1999): Critical percolation on non-amenable groups dies out. Conjectured characterization of non-amenability with percolation. Harmonic Dirichlet functions, Uniform Spanning Forests, L^2-Betti numbers. Sofic groups. Quasi-isometries and embeddings of metric spaces.

Prerequisites: The core courses Real Analysis and Algebra are recommended. Former exposure to probability (e.g., the graduate probability courses) would be helpful.

Some references we will use:

S. Hoory, N. Linial and A. Wigderson:  Expander graphs and their applications, Bulletin of AMS, 2006,
http://www.cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf

M. Kapovich: Lectures on geometric group theory,
http://www.math.ucdavis.edu/~kapovich/EPR/ggt.pdf

A. Lubotzky: Discrete groups, expanding graphs and invariant measures,
Progress in Math. 125, Birkhauser Verlag, Basel, 1994.

R. Lyons with Y. Peres: Probability on trees and networks,
http://mypage.iu.edu/~rdlyons/prbtree/prbtree.html

W. Woess: Random walks on infinite graphs and groups, Cambridge University Press, 2000.