Unit information: Topics in Discrete Mathematics 34 in 2015/16

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

Description including Unit Aims

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/

Intended Learning Outcomes

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.

Teaching Information

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.

Assessment Information

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.

Reading and References

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.