OverviewCombinatorics 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.
This module appears in:
42-48 lectures and example classes
Method of assessment
80% Examination, 20% Coursework
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).
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.