Graphs and Combinatorics - MA595

Location Term Level Credits (ECTS) Current Convenor 2017-18 2018-19
Canterbury Spring
View Timetable
6 15 (7.5) DR CD Bowman-Scargill

Pre-requisites

None

Restrictions

None

2017-18

Overview

Combinatorics is a field in mathematics that studies discrete, usually finite, structures, such as graphs. It not only plays an important role in numerous parts of mathematics, but also has real world applications. In particular, it underpins a variety of computational processes used in digital technologies and the design of computing hardware.
Among other things, this module provides an introduction to graph theory. Graphs are discrete objects consisting of vertices that are connected by edges. We will discuss a variety of concepts and results in graph theory, and some fundamental graph algorithms. Topics may include, but are not restricted to: trees, shortest paths problems, walks on graphs, graph colourings and embeddings, flows and matchings, and matrices and graphs.
In addition to graphs, the module may cover other topics in combinatorics such as: problems in extremal set theory, enumerative problems, Principle of Inclusion and Exclusion, and, for M-level students, Ramsey theory, computational complexity and the P versus NP problem.

Details

This module appears in:


Contact hours

42-48 lectures and example classes

Method of assessment

80% Examination, 20% Coursework

Preliminary reading

P. Cameron, Combinatorics, Topics, Techniques Algorithms, Cambridge Press, (1994)
L. Lovasz, J. Pelikan, and K. Vesztergombi, Discrete Mathematics: Elementary and Beyond. Springer-Verlag, (2003).
D. B. West, Introduction to Graph Theory, Prentice Hall, (1996).
R.J. Wilson, Introduction to Graph Theory, Fourth edition. Longman, Harlow, (1996).

See the library reading list for this module (Canterbury)

See the library reading list for this module (Medway)

Learning outcomes

On successful completion of this module, students will:
1 have gained knowledge of the fundamental concepts and results in graph theory and combinatorics;
2 be able to describe and solve a mathematical problem using graphs and combinatorial arguments;
3 have gained further knowledge of discrete structures in mathematics;
4 have gained a working knowledge of various fundamental graph algorithms;
5 have an ability to understand constructive proofs and to be able to use them to design algorithms.

University of Kent makes every effort to ensure that module information is accurate for the relevant academic session and to provide educational services as described. However, courses, services and other matters may be subject to change. Please read our full disclaimer.