Discrete Mathematics

BUEM002S5 (30 credits)

Aims

This module aims to develop the ideas and techniques of combinatorics and graph theory, and use them for modelling problems in the social sciences.

Teaching and Assessment

Teaching for this module will take place throughout the year, with eight evenings in each of the Autumn and Spring Terms and two evenings of revision and consolidation in the Summer Term.

Of the final course mark, 80% is based on a three-hour exam in June and the other 20% is from assessed coursework.

Coursework will consist of short, problem based assignments. You will have around three weeks to complete each one.

The examination in the Summer Term has two sections. Section A (worth 40%) consists of compulsory short questions. Section B (also worth 40%) contains several longer questions of which you must answer two.

Syllabus

Sequences and  Counting
Arithmetic and geometric progressions, the sequences un=Run-1+d and un=n k  (k=1,2,3,4), the rule of sum, the rule of product, r-sequences, r-permutations, r-combinations, r-multisets, distribution problems, binomial coefficients,
The pigeon hole principle, the inclusion-exclusion theorem.

Generating Functions
Power series, finding the generating function of a problem, finding the coefficients of a generating function, application of generating functions to sequences.

Difference Equations
Linear difference equations, homogeneous difference equations, first order difference equations, second order linear difference equations with constant coefficients, modelling simple problems in finance and economics using difference equations, population models, cobweb diagrams, the discrete logistic equation, Catalan numbers, using generating functions to solve difference equations.

Basic Graph Theory
Vertices and edges, simple graphs, the degree of a vertex, the degree sequence of a graph, the handshaking lemma, subgraphs, isomorphic graphs, null and complete graphs, cycles and paths, platonic graphs, connectedness, planar graphs, trees, weighted graphs, digraphs, networks.

Trees
Trees and forests, characterisations of a tree, spanning trees, minimum connector, Kruskal’s and Prim’s algorithms, labelled trees, Cayley’s Theorem for labelled trees.

Traversability
Cycles, Eulerian graphs, Fleury’s algorithm, semi-Eulerian graphs, Hamiltonian cycles, Ore’s Theorem, Dirac’s Theorem, the travelling salesman problem

Path problems
Paths, connectedness, vertex and edge-disjoint paths between two vertices, separating sets, Menger’s Theorem, networks, shortest path problem, longest path problem, scheduling problems, flows on a network, cuts in a network, the maximum flow-minimum cut theorem.

Matching Problems
Pairings, matchings in graphs, bipartite graphs, perfect, complete, maximal and maximum matchings in a graph, Hall’s Theorem, stable matchings, optimal assignments, the Hungarian algorithm, the bottleneck problem.

Learning Outcomes

Subject Specific

Knowledge and understanding of, and the ability to use, mathematical and/or statistical techniques. In particular:

• Counting techniques, including generating functions;
• Methods of solution of ordinary difference equations;
• Techniques of graph theory, including algorithms for solving tree, path, cycle and matching problems;

Knowledge and understanding of a range of results in mathematics. In particular:

• Theorems in combinatorics; for example, the inclusion-exclusion theorem and the pigeon hole principle;
• Theorems in graph theory; for example, Dirac’s Theorem and Hall’s Theorem

Appreciation of the need for proof in mathematics, and the ability to follow and construct mathematical arguments. In particular:

• Knowledge of the theory underpinning combinatorics and graph theory.;
• Ability to produce proofs using combinatorial and graph theoretic ideas.

Awareness of the use of mathematics and/or statistics to model problems in the natural and social sciences, and the ability to formulate such problems using appropriate notation. In particular:

• Modelling problems in the social sciences.

Knowledge and understanding of a range of modelling techniques, their conditions and limitations, and the need to validate and revise models. In particular:

• Modelling problems using difference equation;
• Modelling problems using graphs and networks, and applying algorithms to find their solution.

A deeper knowledge of some particular areas of mathematics.

Intellectual

Ability to comprehend conceptual and abstract material.
Develop a logical and systematic approach to problem solving.

Practical

Ability to use a range of software packages including word processing and spreadsheets.
Problem-solving skills, including the ability to assess problems logically and to approach them analytically.
Highly developed quantitative skills
Ability to transfer knowledge and expertise from one context to another.

Personal and Social

Ability to learn independently using a variety of media.
Ability to work independently with patience and persistence.
Time-management and organizational skills.
General IT skills, including word processing and spreadsheets.
Good communication skills, including the ability to write coherently.
Ability to complete a sustained and substantial task.
Ability to complete work in a limited time period.

Recommended Books

(provisional list)

• Grimaldi, RP, Discrete and Combinatorial Mathematics: An Applied Introduction, Addison Wesley.
• Jackson, BW and D Thoro, Applied Combinatorics with Problem Solving, Addison Wesley.
• Tucker, A, Applied Combinatorics, Wiley.
• Townsend, M, Discrete Mathematics: Applied Combinatorics and Graph Theory, Benjamin-Cummings.
• Wilson, RJ and JJ Watkins, Graphs: An Introductory Approach, Wiley.
• Biggs, NL, Discrete Mathematics, Oxford.
• Balakrishnan, VK, Introductory Discrete Mathematics, Prentice Hall.