MAT 1045HF
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.

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,

M. Kapovich: Lectures on geometric group theory,

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

R. Lyons with Y. Peres: Probability on trees and networks,

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