Spectra and geometry of graphs and networks (MAGIC096) |
GeneralDescription
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.
SemesterAutumn 2017 (Monday, October 9 to Friday, December 15) Timetable
PrerequisitesThe 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.
SyllabusNo syllabus information is available yet.
Lecturer
Students
Bibliography
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.) AssessmentNo assessment information is available yet.
No assignments have been set for this course. FilesNo files have yet been uploaded for this course. Recorded LecturesPlease log in to view lecture recordings. |