Unit name | Topics in Discrete Mathematics 34 |
---|---|

Unit code | MATHM0009 |

Credit points | 10 |

Level of study | M/7 |

Teaching block(s) |
Teaching Block 2C (weeks 13 - 18) |

Unit director | Dr. Wolf |

Open unit status | Not open |

Pre-requisites |
Students must have taken at least two of the following units: MATH20200 (Metric Spaces), MATH21800 (Algebra 2), MATH21400 (Linear Algebra 2). For joint Mathematics 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 H/6 unit Topics in Discrete Mathematics 3. |

Co-requisites |
None |

School/department | School of Mathematics |

Faculty | Faculty of Science |

Unit aims

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.

General Description of the Unit

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. Combinatorics is a huge subject, but a very accessible one.

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 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.

Relation to Other Units

The course will complement the Complex Networks unit in Mathematics and the Data Structures and Algorithms unit in Computer Science.

Further information is available on the School of Mathematics website: http://www.maths.bris.ac.uk/study/undergrad/

Learning Objectives

Students who successfully complete the unit should be able to:

- recognise and use for problem solving the principal methods of discrete counting and combinatorial structures associated with them;
- define the key concepts of graph theory and use graph structures to represent data sets and relations on them;
- design discrete mathematical models for applications, and derive and calculate relevant properties.

By pursuing an individual project on a more advanced topic students should have:

- developed an awareness of a broader literature;
- gained an appreciation of how the basic ideas may be further developed;
- learned how to assimilate material from several sources into a coherent document.

Transferable Skills

The ability to think clearly about discrete structures and the ability to analyse complex real-world problems using combinatorial abstractions.

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.

80% Examination and 20% Coursework.

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.

Lecture notes and handouts will be provided covering all the main material.

The following supplementary texts provide background reading:

- Peter J. Cameron. Combinatorics: Topics, Techniques, Algorithms. CUP, 1995.

- R. P. Grimaldi. Discrete and Combinatorial Mathematics: An Applied Introduction, 5th ed. Addison Wesley, 2003.

- Dieter Jungnickel. Graphs, networks, and algorithms. Springer, 2005.

- Ian Anderson. A First Course in Discrete Mathematics. Springer, 2001.

- Alan Camina and Barry Lewis. An Introduction to Enumeration. Springer, ,2011.