Back to the home page of A.Grigor'yan

WS 2009/2010 

Analysis on graphs (240027)

12.10.2009 - 05.02.2010

Timetable of lectures

  1. Mo 12:15-13:45   H8
  2. Di   16:00-17:45   H16

Prerequisites

Linear Algebra, Analysis I, Probability I (elementary probability theory only)

Syllabus

1. Introduction: Laplace operators and Markov chains on graphs

A discrete Laplace operator on ZN and on an arbitrary locally finite graph. Weighted graphs and weighted 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.

2. The spectrum of the Laplace operator on a finite graph

The boundaries of the spectrum and the simplicity of the bottom eigenfunction. The variational characterization of the eigenvalues. The first eigenvalue l1 of the Laplace operator . The convergence to equilibrium for a random walk (Perron-Frobenius theorem). The rate of convergence to the equilibrium. Eigenvalues on products.

3. Geometric bounds of eigenvalues

Isoperimetric inequalities and Cheeger's  inequality.  Estimating l1 from below via diameter.  Estimating l from above via distances and measures. The concentration phenomenon. Expansion rate.

4. The Dirichlet Laplace operator on an infinite graph

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 ZN. 

5. The heat kernel and the type problem

The notion of the heat kernel (the transition density) of a random walk.  On-diagonal upper bounds of heat kernels via Faber-Krahn inequality. On-diagonal lower bounds of the heat kernel via volume function and l1. The type problem: recurrence versus transience of a random walk.  The Nash-Williams test for recurrence.  An isoperimetric test for transience. Polya's theorem on the type of a random walk in ZN.  Estimates of the return probabilities on Cayley graphs . The type problem on Cayley graphs.

Bibliography

  1. Chung F.R.K., Spectral Graph Theory,  CBMS Regional Conference Series in Mathematics 92,
    AMS publications, 1996. ISBN 0-8218-0315-8, library of Bielefeld University  QA052%Y94 C559
    online resource
  2. Doyle P.G., Snell J.L.}, Random walks and electric networks, Carus Mathematical Monographs 22,
    Mathematical Association of America, Washington, DC, 1984.
    ISBN 0-88385-024-9, library of Bielefeld University QC540 D754.
    online resource
  3. Saloff-Coste L., Lectures on finite Markov chains, in: "Lectures on probability theory and statistics",
    Lecture Notes Math. 1665, Springer, 1997. pp. 301-413.
    ISBN 3-540-63190-9, library of Bielefeld University QA052%Y96 E1E8P.
    online resource
  4. Woess W., Random walks on infinite graphs and groups, Cambridge Tracts in Mathematics 138,
    Cambridge Univ. Press., 2000.
    ISBN 0-521-55292-3, library of Bielefeld University QB120 W843.