Back to the home page of A.Grigor'yan
10.10.2011 - 03.02.2012
Linear Algebra, Analysis I, Probability I (elementary probability theory only)
Graphs, weighted graphs, Cayley graphs. A discrete Laplace operator. The maximum principle and the solvability of the Dirichlet problem. Definition of a Markov kernel and a Markov chain. Transition probability. Reversibility. Random walk on a weighted graph as a reversible Markov chain. The notion of ergodicity of Markov chains.
The boundaries of the eigenvalues lk of the Laplace operator. Variational characterization of the eigenvalues. Convergence to equilibrium for a random walk on non-bipartite and bipartite graphs (Perron-Frobenius theorem for reversible Markov chain). Rate of convergence to the equilibrium. Eigenvalues on products of graphs.
Cheeger's constant and Cheeger's inequality. Estimating distances between sets via measure and eigenvalues. The concentration phenomenon. Expansion rate of sets and vertices.
Definition of the Dirichlet Laplacian (with boundary condition). Cheeger's inequality for the Dirichlet eigenvalues. Solving the Dirichlet problem by iterations. Isoperimetric inequality on Cayley graphs of finitely generated groups. Isoperimetric inequality in Zm.
The notion of the heat kernel (the transition density) of a random walk. Estimates of the heat kernel for one-dimensional random walk. Carne-Varopoulos estimate for an arbitrary graph. On-diagonal upper bounds of heat kernels via Faber-Krahn inequality. On-diagonal lower bounds of the heat kernel via volume function and l1. Heat kernel on groups of polynomial volume growth.
The type problem: recurrence versus transience of a random walk. Reduction to heat kernel. Polya's theorem on the type of a random walk in Zm. The type problem on Cayley graphs. The Nash-Williams test for recurrence. An isoperimetric test for transience.