Breadcrumb

Topics in Discrete Mathematics 3 (MATH30002)

Academic Year:

Contents of this document:

Administrative Information

  1. Unit number and title: MATH30002 Topics in Discrete Mathematics 3
  2. Level: H/6
  3. Credit point value: 10 credit points
  4. Year: 12/13
  5. First Given in this form: 2012
  6. Unit Organiser: Misha Rudnev
  7. Lecturer: Edward Crane, Tom McCourt and Graeme Taylor
  8. Teaching block: 2
  9. Prerequisites: 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 M/7 unit Topics in Discrete Mathematics 34.

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.

Teaching Methods

Lectures, including examples and revision classes, supported by lecture notes with problem sets and model solutions.

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.

Assessment Methods

The final assessment mark will be entirely based on a 1½-hour written examination in May-June consisting of THREE questions. A candidate's best TWO answers will be used for assessment. Calculators are NOT permitted in this examination.

Award of Credit Points

Credit points for the unit are gained by passing the unit (i.e. getting a final assessment mark of 40 or over).

Transferable Skills

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

Texts

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.

 

Syllabus

Topics covered will include:

Combinatorial enumeration (counting methods);  foundations of graph theory.

Possible additional topics include:

Hypergraphs; extremal graphs; graph colouring problems; finite geometry; designs;  flows on networks; error-correcting and error-detecting linear codes; partially ordered sets.