杏吧论坛

Dr Ahmad Abdi and Dr Neil Olver

This course is available on the CEMS Exchange, MBA Exchange, MSc in Applicable Mathematics and MSc in Operations Research & Analytics. This course is available with permission as an outside option to students on other programmes where regulations permit.

Basic knowledge of graph theory and linear algebra. In particular, students should be familiar with graph theoretic notions such as spanning trees, cycles, cuts, stable sets, etc. and linear algebraic notions such as eigenvectors, eigenvalues, projections, the characteristic polynomial, etc.

An examination of advanced topics in Operations Research. The topics selected differ year to year; the topic for 2021/22 will be "Spectral Graph Theory".

Spectral Graph Theory is concerned with how combinatorial properties of graphs relate to the algebraic structure of certain matrices associated with the graph. One can look at the adjacency matrix of an undirected graph, which is a symmetric matrix, and consider the list of its eigenvalues, called the spectrum, along with the corresponding eigenvectors. The spectrum gives us important insight about the graph and its induced subgraphs, and perhaps surprisingly, this viewpoint can be used in the design of graph algorithms, such as network flow problems, plane drawings of planar graphs, isomorphism testing, etc.

Some highlights of the course include:

• Eigenvalue interlacing, and applications to graph theory
• Connections to electrical networks, random spanning trees, and random walks
• Spring layout drawings of graphs using spectral methods
• Clustering: how to find good ways of partitioning a graph into pieces via the spectrum
• Expander graphs: sparse graphs with exceptional connectivity properties

2 hours of help sessions in the ST.

This course is delivered through a combination of seminars and lectures totalling a minimum of 35 hours across Lent Term. This year, the lectures will be live, online and recorded. Depending on circumstances, seminars might be live and online, too.

There will be 5 biweekly homework assignments, each of which will be marked and the student will receive feedback.

Algebraic Graph Theory (Springer 2001), by Godsil and Royle.

Spectral and Algebraic Graph Theory (online), by Spielman.

Assessment path 1
Exam (100%, duration: 3 hours) in the spring exam period.

Assessment path 2
Project (100%) in the ST.

Exam (100%, duration 3 hours)

PhD students are expected to complete a research-based project (worth 100%) in the ST as a replacement for the final exam.