Introduction to Analysis on Graphs ( University Lecture Series )

Publication series ： University Lecture Series

Author： Alexander Grigor’yan  

Publisher： American Mathematical Society‎

Publication year： 2018

E-ISBN: 9781470448554

P-ISBN(Paperback): 9781470443979

Subject： O1 Mathematics

Keyword： 数学

Language： ENG

Access to resources Favorite

Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.

Introduction to Analysis on Graphs

Description

Anybody who has ever read a mathematical text of the author would agree that his way of presenting complex material is nothing short of marvelous. This new book showcases again the author's unique ability of presenting challenging topics in a clear and accessible manner, and of guiding the reader with ease to a deep understanding of the subject. —Matthias Keller, University of Potsdam A central object of this book is the discrete Laplace operator on finite and infinite graphs. The eigenvalues of the discrete Laplace operator have long been used in graph theory as a convenient tool for understanding the structure of complex graphs. They can also be used in order to estimate the rate of convergence to equilibrium of a random walk (Markov chain) on finite graphs. For infinite graphs, a study of the heat kernel allows to solve the type problem—a problem of deciding whether the random walk is recurrent or transient. This book starts with elementary properties of the eigenvalues on finite graphs, continues with their estimates and applications, and concludes with heat kernel estimates on infinite graphs and their application to the type problem. The book is suitable for beginners in the subject and accessible to undergraduate and graduate students with a background in linear algebra I and analysis I. It is based on a lecture course taught by the author and includes a wide variety of exercises. The book will help the reader to reach a level of understanding sufficient to start

Chapter

Cover

Title page

Preface

Chapter 1. The Laplace operator on graphs

1.1. The notion of a graph

1.2. Cayley graphs

1.3. Random walks

1.4. The Laplace operator

1.5. The Dirichlet problem

Chapter 2. Spectral properties of the Laplace operator

2.1. Green’s formula

2.2. Eigenvalues of the Laplace operator

2.3. Convergence to equilibrium

2.4. More about the eigenvalues

2.5. Convergence to equilibrium for bipartite graphs

2.6. Eigenvalues of ℤ_{𝕞}

2.7. Products of graphs

2.8. Eigenvalues and mixing time in ℤ_{𝕞}ⁿ, 𝕞 odd.

2.9. Eigenvalues and mixing time in a binary cube

Chapter 3. Geometric bounds for the eigenvalues

3.1. Cheeger’s inequality

3.2. Eigenvalues on a path graph

3.3. Estimating 𝜆₁ via diameter

3.4. Expansion rate

Chapter 4. Eigenvalues on infinite graphs

4.1. Dirichlet Laplace operator

4.2. Cheeger’s inequality

4.3. Isoperimetric and Faber-Krahn inequalities

4.4. Estimating 𝜆₁(Ω) via inradius

4.5. Isoperimetric inequalities on Cayley graphs

4.6. Solving the Dirichlet problem by iterations

Chapter 5. Estimates of the heat kernel

5.1. The notion and basic properties of the heat kernel

5.2. One-dimensional simple random walk

5.3. Carne-Varopoulos estimate

5.4. On-diagonal upper estimates of the heat kernel

5.5. On-diagonal lower bound via the Dirichlet eigenvalues

5.6. On-diagonal lower bound via volume growth

5.7. Escape rate of random walk

Chapter 6. The type problem

6.1. Recurrence and transience

6.2. Recurrence and transience on Cayley graphs

6.3. Volume tests for recurrence

6.4. Isoperimetric tests for transience

Chapter 7. Exercises

Bibliography

Index

Back Cover

The users who browse this book also browse


No browse record.