Back to the home page of A.Grigor'yan

WS 2011/2012 

Analysis on graphs (240027)

10.10.2011 - 03.02.2012

Timetable of lectures

  1. Friday    8:30-10:00  V2-205
  2. Friday  12:30-14:00   V4-119

Tutorials

Thursday 14-16

Prerequisites

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

Syllabus

1. Introduction: Laplace operators and Markov chains on graphs

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.

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

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.

3. Geometric bounds of eigenvalues

Cheeger's constant and Cheeger's  inequality.  Estimating distances between sets via measure and eigenvalues. The concentration phenomenon. Expansion rate of sets and vertices.

4. The Dirichlet Laplace operator and its eigenvalues 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 Zm. 

5. Estimates of the heat kernel

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.  

6. The type problem

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.

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.