Courses in the Department of Mathematics

MA316: Graph Theory

General information about MA316: Graph Theory

This is a new course that will start in the Lent Term. This means that some materials (such as notes, a mock examination paper) will become available during the Lent Term.

Teacher responsible: Dr Jozef Skokan

Room: B303 (Columbia House)

Email: jozef(at)maths.lse.ac.uk

Office hours: Please see the office hours page

Lectures can classes

This is a half-unit course, with lectures in the Lent Term.
Classes start in Week 2 of Term. Please see the Timetables webpage for full details: http://www.lse.ac.uk/admin/timetables/confirmed/module_sessional/ma/19.htm.

There will also be revision lectures in the Summer Term.

Exercises

Homework will be assigned weekly. It is important that students hand in work for marking before each class.
Corrected work will be handed back and, where appropriate, discussed in the classes. Full solutions for the homework exercises will be given out as well. This means that not all exercises need to be discussed in class.

Course material

Lecture notes will be provided. Additionally, students may wish to refer to the following books:

"Discrete Mathematics" by Norman L. Biggs (2nd edition, Oxford University Press, 2002) ISBN: 0198507178;
Library code: QA76.9 M35 B59;
"Introduction to Graph Theory" by D. B. West (Prentice Hall 2001) ISBN: 0130144002;
Library code: QA166 W51;
"Graph Theory with Applications" by J.A.Bondy and U.S.R. Murty (North Holland 1976)
Library code: QA166 B71;

All course material distributed, including lecture notes, exercise sheets and homework solutions, will also be made available via http://www.maths.lse.ac.uk/Courses/MA316/.

Assessment

There will be a formal 2-hour examination in the Summer term. A mock exam paper, with solutions, will be available for download from below.

Course description of MA316: Graph Theory

Overview

This course examines in detail concepts and techniques of graph theory.

Aims

The course is designed to:

enable students to obtain general knowledge about the area of dgraph theory, and more in-depth knowledge of selected topics;
enable students to understand and appreciate the methods used to construct mathematical proofs.

Learning outcomes

After having followed this course, students should

have knowledge of basic definitions and concepts, and how to apply these;
have knowledge of more complicated definitions and concepts, and how to apply these in situations similar to known ones;
have knowledge of the basic techniques and methodologies in the topics covered;
be able to understand new situations and definitions, derive their formal meaning, and relate them to existing knowledge;
be able to model actual situations in a mathematical way and derive useful results.

Connections to Other Courses

MA103: Introduction to Abstract Mathematics is a prerequisite for this course. Students who are not sure if their knowledge is up to the level expected, are advised to contact the lecturer before the start of the course.

The course is aimed at students who are interested in more abstract mathematical ideas. Students who are interested in this type of mathematics should also consider taking MA210: Discrete Mathematics, MA314: Theory of Algorithms, or MA315: Algebra and its Applications. Students who take MA210: Discrete Mathematics can still take this course since the overlap of topics is minimal.

Course Content

The course covers the following topics.

fundamental concepts,
connectivity and matchings,
colourings,
flows,
extremal problems.

Optional topics include Ramsey theory, matroids, spectral graph theory, or random graphs.

Lectures

During the lectures, the theory will be developed and explained, proofs given, and many examples demonstrated. Students are expected to make their own notes during the lecture. In the Summer Term there will be additional lectures, mainly for revision purposes.

Classes and Exercises

In this course, as in other courses in Mathematics, it is very important that all homework questions are attempted and handed in for grading. There is a big difference between watching other people carry out calculations and being able to do them yourself, and it is vital to get practice in the various techniques covered in the course. It is also important to hand in homework, so that feedback on it can be given. Corrected work will be handed back and discussed as soon as possible. A complete set of solutions to the homework exercises will also be made available.

The lecturer of this course pays great attention to the presentation of the homework. It is not enough to have the correct answer, but also the reasoning used to obtain that answer should be correct and understandable. Students will be expected to maintain reasonable standards of written English, to write clear logical arguments, and to use mathematical notation correctly.

Office Hours

The office hours are meant for any questions and problems with the course material that have not or cannot be covered in the normal lectures and classes. You are strongly recommended to make use of them. It is expected that students utilise the office hours of their class teacher.

Mock examination paper

A mock examination paper will appear here in the Lent Term.