MATH32091 – 2019/20
General Information
- Title: Combinatorics and Graph Theory
- Unit code: MATH32091
- Credits: 10
- Prerequisites: 1st and 2nd year core course units
- Co-requisite units: None
- Members of staff responsible: Dr.
Gábor
Megyesi
- Office: Alan Turing Building 2.123
- Tel: 63644
- E-mail: Gabor.Megyesi@manchester.ac.uk
Specification
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.
Brief Description of the unit
A graph consists of a set of vertices with a set of edges connecting
some pairs of 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 to obtain asymptotic formulae for a(n).
Learning Outcomes
On successful completion of the course students will be able to:
- 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 lecture]
- Electrical networks [2]
- Flows in graphs, Max-flow min-cut theorem [3]
- Matching problems [3]
- Extremal problems [3]
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]
- Generating function proofs of the sieve formula and of
various combinatorial identities. Certifying combinatorial identities. [2]
- Some analytical methods and asymptotic results. [2]
Textbooks
Recommended texts:
- B Bollobás, Graph theory, An introductory course (Graduate Texts in
Mathematics 63), Springer, 1979.
- B Bollobás, 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.
Teaching and learning methods
Two lectures and one examples class each week. Students are recommended
to do at least four hours private study each week on the course unit.
Assessment
Coursework test in week 5.
End of semester examination: two hours, weighting 80%