Announcements


There are no announcements

Forum

General


Description

Combinatorial graphs and networks appear in many theoretical and practical contexts. It is beneficial for every working mathematician and theoretical computer scientist to have a good familiarity with these concepts. A very active research area is spectral graph theory, where graphs and their properties are studied via the eigenvalues of their associated adjacency matrices. This topic is particularly appealing since it needs very little background knowledge and leads efficiently to many beautiful and deep observations and results. We will cover various useful aspects of general interest with a geometric viewpoint, amongst them: variational characterisation of eigenvalues, Cheeger isoperimetric constants or expansion rates and inequalities between them and eigenvalues, leading to the timely topics of expander graphs, spectral clustering, construction of codes, Ramanujan graphs, and Cayley graphs as geometric representations of discrete groups. We will discuss fundamental connections between eigenvalues and dynamics like mixing properties of random walks and electrical networks. We will study eigenvalue relations under graph constructions like coverings, zigzag products, and line graphs, and we will also investigate the interplay between eigenvalues and specific discrete curvature notions (like one based on optimal transport). In summary, the course provides a variety of interesting tools which can be used to study graphs and networks both from a geometric and an algebraic viewpoint via eigenvalues.

Semester

Autumn 2017 (Monday, October 9 to Friday, December 15)

Timetable

  • Mon 13:05 - 13:55

Prerequisites

The course will be self contained. Only basic knowledge in linear algebra (linear maps, symmetric matrices, eigenvalues), graph theory (vertices and edges of graphs, graph automorphisms), algebra (discrete groups and generators, symmetry groups), and probability theory (discrete probability spaces) is needed.

Syllabus

No syllabus information is available yet.

Lecturer


Norbert Peyerimhoff
Email norbert.peyerimhoff@durham.ac.uk
Phone 0191 334 3114
Photo of Norbert Peyerimhoff
Profile: My research interests are centered around geometry. Of particular interest are relations between geometry and Laplace- and Schrödinger operators and relations between geometry and dynamical systems. In most cases, the spaces under considerations are non-positively curved or have at least a noncompact covering space. I am also interested in analogues and differences between the continuous setting of Riemannian manifolds and the discrete setting of graphs, in explicit constructions of expander graphs, spectral graph theory, and synthetic curvature notions in discrete spaces.


Students


Photo of Jack Aiston
Jack Aiston
(Newcastle)
Photo of Brennen Fagan
Brennen Fagan
(York)
Photo of Kathryn Laing
Kathryn Laing
(Leeds)
Photo of Johannes Lutzeyer
Johannes Lutzeyer
(*Ext_Assessed)
Photo of Andrea Pachera
Andrea Pachera
(Birmingham)
Photo of Motiejus Valiunas
Motiejus Valiunas
(Southampton)


Bibliography


Algebraic Graph TheoryNorman Biggs
Spectra of GraphsAndries E. Brouwer and Willem H. Haemers
Expander Families and Cayley Graphs - A Beginner's guideMike Krebs and Anthony Shaheen
Random Walks and Electric NetworksPeter G. Doyle and J. Laurie Snell
Spectral Graph TheoryFan R. K. Chung
Spectral Clustering and Biclustering - Learning Large Graphs and Contingency TablesMarianna Bolla
Google's PageRank and Beyond - The Science of Search Engine RankingsAmy N Langville and Carl D Meyer
Introduction to Coding TheoryRon M Roth


Note:

Clicking on the link for a book will take you to the relevant Google Book Search page. You may be able to preview the book there. On the right hand side you will see links to places where you can buy the book. There is also link marked 'Find this book in a library'. This sometimes works well, but not always. (You will need to enter your location, but it will be saved after you do that for the first time.)

Assessment



No assessment information is available yet.

No assignments have been set for this course.

Files



No files have yet been uploaded for this course.

Recorded Lectures


Please log in to view lecture recordings.