Not available in 2023/24
MA431      Half Unit
Advanced Topics in Operations Research and Applicable Mathematics

This information is for the 2023/24 session.

Teacher responsible

Dr Ahmad Abdi and Dr Neil Olver

Availability

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.

Pre-requisites

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.

Course content

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

Teaching

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.

Formative coursework

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

Indicative reading

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

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

Assessment

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.

Key facts

Department: Mathematics

Total students 2022/23: Unavailable

Average class size 2022/23: Unavailable

Controlled access 2022/23: No

Value: Half Unit

Guidelines for interpreting course guide information

Course selection videos

Some departments have produced short videos to introduce their courses. Please refer to the course selection videos index page for further information.

Personal development skills

  • Problem solving
  • Application of numeracy skills
  • Specialist skills