##
MA408 Half Unit

Discrete Mathematics and Graph Theory

**This information is for the 2017/18 session.**

**Teacher responsible**

Prof Jozef Skokan

**Availability**

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

**Pre-requisites**

Students should be taking the course MA407 Algorithms and Computation or have taken an equivalent course to provide a basic knowledge of algorithms, and should have experience with proofs and proof techniques used in pure mathematics.

**Course content**

This course provides an introduction to discrete mathematics, particularly graph theory. Emphasis will be placed on the algorithmic aspects of the area.

Topics to be covered include: Brief Introduction to discrete mathematics and graph theoretic terminology; Ramsey's Theorem; matchings and Hall's Theorem; graph search algorithms; stable marriages and the Gale-Shapley Theorem; network flows and the Ford-Fulkerson Theorem; connectivity and Menger's Theorems; graph colouring and Brooks' Theorem; an introduction to the probabilistic method; spectral graph theory and random walks.

**Teaching**

20 hours of lectures and 15 hours of seminars in the MT. 2 hours of lectures in the ST.

**Formative coursework**

Students will be expected to produce 10 exercises in the MT.

Weekly exercises are set and marked.

**Indicative reading**

Norman L. Biggs, Discrete Mathematics, Oxford University Press; T H Cormen, C E Leiserson & R Rivest and C Stein, Introduction to Algorithms, Cambridge University Press; R Diestel, Graph Theory, Springer; H S Wilf, Algorithms and Complexity, Prentice Hall.

Several of these texts are available online. More information, plus additional notes, will be provided during the course.

**Assessment**

Exam (75%, duration: 2 hours) in the main exam period.

Coursework (25%) in the MT.

** Key facts **

Department: Mathematics

Total students 2016/17: 5

Average class size 2016/17: 5

Controlled access 2016/17: No

Value: Half Unit

**Personal development skills**

- Self-management
- Problem solving
- Application of information skills
- Communication
- Application of numeracy skills
- Specialist skills