MMath Mathematics and Statistics / Course details

Year of entry: 2024

Course unit details:
Combinatorics and Graph Theory

Course unit fact file
Unit code MATH32091
Credit rating 10
Unit level Level 3
Teaching period(s) Semester 1
Offered by Department of Mathematics
Available as a free choice unit? No

Overview

A graph consists of a set of vertices with a set of edges connecting some pairs vertices. Depending on the context, the edges may represent a mathematical relation, two people knowing each other or roads connecting towns, etc. The graph theory part of the course deals with networks, structure of graphs, and extremal problems involving graphs.

The combinatorial half of this course is concerned with enumeration, that is, given a family of problems P(n), n a natural number, find a(n), the number of solutions of P(n) for each such n. The basic device is the generating function, a function F(t) that can be found directly from a description of the problem and for which there exists an expansion in the form F(t) = sum {a(n)gn(t); n a natural number}. Generating functions are also used to prove a family of counting formulae to prove combinatorial identities and obtain asymptotic formulae for a(n).

Pre/co-requisites

Unit title Unit code Requirement type Description
Calculus and Vectors A MATH10121 Pre-Requisite Compulsory
Calculus and Vectors B MATH10131 Pre-Requisite Compulsory
Linear Algebra A MATH10202 Pre-Requisite Compulsory
Linear Algebra B MATH10212 Pre-Requisite Compulsory

Aims

To introduce the students to graphs, their properties and their applications as models of networks.

To introduce the students to generating functions and their applications.

Learning outcomes

On successful completion of the course students will be: 

  • define graph theoretic concepts, state and prove their properties,
  • describe graph theoretic algorithms and prove their correctness,
  • formulate problems in terms of graphs and apply the theorems and algorithms taught in the course to solve them,
  • define the various types of generating functions,
  • state and prove the basic properties of generating functions,
  • use generating functions to solve a variety of combinatorial problems.

 

Syllabus

Graph Theory:

Introduction. [1]   

Electrical networks. [3]   

Flows in graphs, Max-flow min-cut theorem. [3]   

Connectivity and matching problems. [3]   

Extremal problems. [2] 

Combinatorics:   

Examples using ordinary power series and exponential generating functions, general properties of such functions. [3]   

Dirichlet Series as generating functions. [1]   

A general family of problems described in terms of 'cards, decks and hands  with solution methods using generating functions. [3]   

Some analytical methods and asymptotic results. [1]   

Generating function proofs of the sieve formula and of various combinatorial identities. [2]

Assessment methods

Method Weight
Other 30%
Written exam 70%
  • Coursework: weightinng 30%
  • End of semester examination: weighting 70%

Feedback methods

Feedback tutorials will provide an opportunity for students' work to be discussed and provide feedback on their understanding.  Coursework or in-class tests (where applicable) also provide an opportunity for students to receive feedback.  Students can also get feedback on their understanding directly from the lecturer, for example during the lecturer's office hour.
 

Recommended reading

  • B Bollobas, Graph theory, An introductory course (Graduate Texts in Mathematics 63), Springer, 1979.
  • B Bollobas, Modern graph theory, (Graduate Texts in Mathematics 184), Springer, 1998.
  • D Jungnickel, Graphs, Networks and Algorithms (Algorithms & Computation in Mathematics 5), Springer, 1998.
  • H S Wilf, generatingfunctionology, A K Peters, 3rd ed., 2006.

Study hours

Scheduled activity hours
Lectures 11
Tutorials 11
Independent study hours
Independent study 78

Teaching staff

Staff member Role
Gabor Megyesi Unit coordinator

Additional notes

The independent study hours will normally comprise the following. During each week of the taught part of the semester:
 
•         You will normally have approximately 60-75 minutes of video content. Normally you would spend approximately 2-2.5 hrs per week studying this content independently
•         You will normally have exercise or problem sheets, on which you might spend approximately 1.5hrs per week
•         There may be other tasks assigned to you on Blackboard, for example short quizzes or short-answer formative exercises
•         In some weeks you may be preparing coursework or revising for mid-semester tests
 
Together with the timetabled classes, you should be spending approximately 6 hours per week on this course unit.
The remaining independent study time comprises revision for and taking the end-of-semester assessment.
 
The above times are indicative only and may vary depending on the week and the course unit. More information can be found on the course unit’s Blackboard page.

Return to course details