| Unit name | Combinatorics |
|---|---|
| Unit code | MATH20002 |
| Credit points | 20 |
| Level of study | I/5 |
| Teaching block(s) |
Teaching Block 1 (weeks 1 - 12) |
| Unit director | Dr. Harris |
| Open unit status | Not open |
| Pre-requisites |
MATH10010 Introduction to Proofs and Group Theory, MATH10011 Analysis, MATH10013 Probability and Statistics and MATH10015 Linear Algebra |
| Co-requisites |
None |
| School/department | School of Mathematics |
| Faculty | Faculty of Science |
Unit Aims
This unit serves as an introduction to combinatorics, developing fundamental aspects of a diverse range of topics in discrete mathematics such as enumeration, extremal graph theory, Ramsey theory and random walks. The unit aims to develop and improve students’ problem-solving and theorem-proving skills, building on those acquired in first-year courses. Moreover, it seeks to enhance students’ appreciation of the interconnectedness of different areas of mathematics by introducing probabilistic, analytic and algebraic techniques.
Unit Description
Combinatorics is the study of discrete structures, which are ubiquitous in our everyday lives. While combinatorics has important practical applications (for example to networking, optimisation, and statistical physics), problems of a combinatorial nature also arise in many areas of pure mathematics such as algebra, probability, topology and geometry.
The course will start with a revision of various enumeration techniques. The unit will then proceed to introduce the basic notions and fundamental results of graph theory, including Turán’s theorem on independent sets, Hall’s marriage theorem, Euler’s formula for planar graphs and Kuratowski’s theorem. In the last part of the unit probabilistic and algebraic methods will be used to study more advanced topics in graph theory, including Ramsey’s theorem and random walks.
Students who successfully complete the unit should: be proficient at enumeration, rearrangements of finite sets; be familiar with the basic definitions and concepts in graph theory, including trees, cycles, connectivity, matchings, planarity; understand, be able to prove and apply the fundamental results derived in the course, and solve unseen problems of a similar kind; understand and be able to apply methods from elementary probability, analysis and linear algebra to a range of problems in discrete mathematics, including Ramsey theory, isoperimetry and random walks.
In addition, students should have learnt how to give a mathematical formulation to word problems of a discrete nature; improved their problem-solving and theorem-proving skills; gained an appreciation of how methods from probability, analysis and algebra can be used to solve problems in discrete mathematics.
The unit will be taught through a combination of
Raw scores on the examinations will be determined according to the marking scheme written on the examination paper. The marking scheme, indicating the maximum score per question, is a guide to the relative weighting of the questions. Raw scores are moderated as described in the Undergraduate Handbook.
If you fail this unit and are required to resit, reassessment is by a written examination in the August/September Resit and Supplementary exam period.
If this unit has a Resource List, you will normally find a link to it in the Blackboard area for the unit. Sometimes there will be a separate link for each weekly topic.
If you are unable to access a list through Blackboard, you can also find it via the Resource Lists homepage. Search for the list by the unit name or code (e.g. MATH20002).
How much time the unit requires
Each credit equates to 10 hours of total student input. For example a 20 credit unit will take you 200 hours
of study to complete. Your total learning time is made up of contact time, directed learning tasks,
independent learning and assessment activity.
See the Faculty workload statement relating to this unit for more information.
Assessment
The Board of Examiners will consider all cases where students have failed or not completed the assessments required for credit.
The Board considers each student's outcomes across all the units which contribute to each year's programme of study. If you have self-certificated your absence from an
assessment, you will normally be required to complete it the next time it runs (this is usually in the next assessment period).
The Board of Examiners will take into account any extenuating circumstances and operates
within the Regulations and Code of Practice for Taught Programmes.
