| Unit name | Topics in Discrete Mathematics 3 |
|---|---|
| Unit code | MATH30002 |
| Credit points | 10 |
| Level of study | H/6 |
| Teaching block(s) |
Teaching Block 2 (weeks 13 - 24) |
| Unit director | Professor. Misha Rudnev |
| Open unit status | Not open |
| Pre-requisites |
Students must have taken at least two of the following units: MATH 20200 (Metric Spaces), MATH 21800 (Algebra 2), MATH 21400 (Linear Algebra 2). For joint maths and computer science students, it would be desirable to have taken COMS21103 (Data Structures and Algorithms). Students may not take this unit if they have taken the corresponding Level M/7 unit Topics in Discrete Mathematics 34. |
| Co-requisites |
None |
| School/department | School of Mathematics |
| Faculty | Faculty of Science |
Discrete mathematics refers to the study of mathematical structures that are discrete in nature rather than continuous, for example graphs, lattices, partially ordered sets, designs and codes. It is a classical subject that has become very important in real-world applications, and consequently it is a very active research topic.
The core of discrete mathematics is called combinatorics. It deals with the properties of patterns of relationships between objects, and their mathematical representations, for example graphs or a partially ordered set. This unit will cover the key combinatorial topics of combinatorial enumeration (sophisticated counting methods) and graph theory, and then a selection of more specialised topics and applications. Possible topics include network flows, extremal graph theory, hypergraphs, designs and intersecting set systems, error-correcting and detecting codes, combinatorial algorithms, and Ramsey theory (finding ordered substructures in large disordered structures).
The aim of this unit is to introduce students to foundational aspects of combinatorial mathematics via a selection of topics, ranging from the classical, for example Euler tours (the famous Königsberg bridges problem) and Hamiltonian cycles, to the modern, for example experimental designs and properties of real-world social and communications graphs.
The unit will be useful and accessible not only for pure mathematics students, but also for those inclined towards computer science, statistics or logic. Students will learn some ways in which discrete mathematics is important in commercial applications, and they will discover that they can quickly reach fascinating and deep problems that can be explained using only a few simple definitions.
At its core the unit will cover the main counting techniques and the foundations of graph theory. These will constitute a basis for subsequent lectures on a selection of more advanced topics, described above. Care will be taken to avoid too much overlap with the Complex Networks unit in Mathematics and the Data Structures and Algorithms unit in Computer Science.
Students who successfully complete the unit should be able to:
Lectures, including examples and revision classes, supported by lecture notes with problem sets and model solutions. Self-study with directed reading based on recommended material.
Formative assessment will be provided by problem sheets with questions that will be set and marked throughout the course.
The final assessment mark will be based on a 1½-hour written examination (100%).
Lecture notes and handouts will be provided covering all the main material.
The following supplementary texts provide background reading:
