Topics in Discrete Mathematics 3

Unit aims

This is a topics course aimed at deepening and broadening the students' knowledge of various aspects of discrete mathematics, as well as illustrating connections between discrete mathematics and other areas such as algebra, probability, number theory, analysis and computer science.

Unit description

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.

This topics course exposes the students to a selection of advanced topics in discrete mathematics. These may include (but are not restricted to) advanced topics in graph and hypergraph theory, design and coding theory, combinatorial topics in group theory, as well as probabilistic, algebraic and Fourier-analytic methods throughout discrete mathematics.

While results and problems of recent origin may be included in the syllabus, the instructors aim to make the material accessible to all students fulfilling the prerequisites by providing complete lectures notes and including all necessary background material.

The unit is suitable for students with a firm grasp of the basic concepts in the 2nd year combinatorics course, and likely of interest to those with an interest in number theory, algebra, probability and/or theoretical computer science.

Relation to other units

The course follows on from Combinatorics and complements Complex Networks and Data Structures and Algorithms in Computer Science.

Learning objectives

In accordance with the specific syllabus taught in any particular year, students who successfully complete the unit should:

• have developed a solid understanding of the advanced concepts covered in the course;
• be able to use techniques from algebra, analysis and probability to solve problems in discrete mathematics;
• have a good grasp of the applications of combinatorial techniques in other areas of mathematics and to real-world problems.

Transferable skills

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

Syllabus

Topics covered might include (but are not restricted to) any of the following:

• random graphs
• permutation groups
• introduction to the theory of hypergraphs
• advanced topics in design and coding theory
• random walks on groups
• probabilistic methods in combinatorics
• discrete Fourier analysis and applications
• connections with information theory and algorithms

Lecture notes and handouts will be provided covering all the main material. The following supplementary texts provide background reading prior to the start of the course:

• Peter J. Cameron, Combinatorics: Topics, Techniques, Algorithms. CUP, 1995.
• A. Bondy and Murphy, Graph theory, Springer, 2007.
• Ian Anderson, A First Course in Discrete Mathematics. Springer, 2001.

Unit code: MATH30002
Level of study: H/6
Credit points: 10
Teaching block (weeks): 2 (13-18)
Lecturers: Dr Alex Malcolm and Dr Dan Martin

Pre-requisites

Students must have taken MATH20002 Combinatorics and one of MATH21800 Algebra 2, MATH21100 Linear Algebra 2. For joint Mathematics and Computer Science students, it would be desirable to have taken COMS21103 Data Structures and Algorithms.

None

Methods of teaching

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

Methods of Assessment

The pass mark for this unit is 40.

The final mark is calculated as follows:

• 100% from a 1 hour 30 minute exam in May/June

NOTE: Calculators are NOT allowed in the examination.

For information resit arrangements, please see the re-sit page on the intranet.

Please use these links for further information on relative weighting and marking criteria.

Further exam information can be found on the Maths Intranet.