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 for level 7 students, the module will cover an advanced topic in combinatorics such as: problems in extremal set theory; enumerative problems; Principle of Inclusion and Exclusion; Ramsey theory; computational complexity; the P versus NP problem.
This module appears in:
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).
J.A. Bondy and U.S.R. Murty, Graph Theory, Graduate Text in Math. 244, Springer-Verlag, (2008).
B. Ballobas, Modern Graph Theory, Graduate Text in Math., 184, Springer-Verlag, 1998.
The intended subject specific learning outcomes. On successfully completing the level 7 module students will be able to:
1 demonstrate systematic understanding of Graphs and Combinatorics;
2 demonstrate the capability to solve complex problems using a very good level of skill in calculation and manipulation of the material in the following areas: trees, shortest paths problems, walks on graphs, graph colourings and embeddings, flows and matchings, matrices and graphs;
3 apply a range of concepts and principles in Graphs and Combinatorics theory in loosely defined contexts, showing good judgment in the selection and application of tools and techniques.
The intended generic learning outcomes. On successfully completing the level 7 module students will be able to:
1 work competently and independently, be aware of their own strengths and understand when help is needed;
2 demonstrate a high level of capability in developing and evaluating logical arguments;
3 communicate arguments confidently with the effective and accurate conveyance of conclusions;
4 manage their time and use their organisational skills to plan and implement efficient and effective modes of working;
5 solve problems relating to qualitative and quantitative information;
6 make effective use of information technology skills such as online resources (Moodle), internet communication;
7 communicate technical material effectively;
8 demonstrate an increased level of skill in numeracy and computation;
9 demonstrate the acquisition of the study skills needed for continuing professional development.