##
MA431 Half Unit

Advanced Topics in Operations Research and Applicable Mathematics

**This information is for the 2021/22 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 summer 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.

**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.

**Important information in response to COVID-19**

Please note that during 2021/22 academic year some variation to teaching and learning activities may be required to respond to changes in public health advice and/or to account for the differing needs of students in attendance on campus and those who might be studying online. For example, this may involve changes to the mode of teaching delivery and/or the format or weighting of assessments. Changes will only be made if required and students will be notified about any changes to teaching or assessment plans at the earliest opportunity.

** Key facts **

Department: Mathematics

Total students 2020/21: Unavailable

Average class size 2020/21: Unavailable

Controlled access 2020/21: No

Value: Half Unit

**Personal development skills**

- Problem solving
- Application of numeracy skills
- Specialist skills