MATH39001 - 2008/2009

 

Specification

Aims

Brief Description of the unit

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)g_n(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).

Learning Outcomes

On successful completion of the course students will be:

• able to formulate problems in terms of graphs, solve graph theoretic problems and apply algorithms taught in the course;
• able to use generating functions to solve a variety of combinatorial problems.

Future topics requiring this course unit

None.

Syllabus

Graph Theory
1. Introduction. [1 lecture]
2. Electrical networks. [2]
3. Flows in graphs, Max-flow min-cut theorem. [3]
4. Matching problems. [3]
5. Extremal problems. [3]


Combinatorics

6. Examples using ordinary power series and exponential generating functions, general properties of such functions. [3]
7. Dirichlet Series as generating functions. [1]
8. A general family of problems described in terms of "cards, decks and hands" with solution methods using generating functions. [3]
9. Generating function proofs of the sieve formula and of various combinatorial identities. Certifying combinatorial identities. [2]
10. Some analytical methods and asymptotic results. [2]

Textbooks

Recommended texts:

• H S Wilf, generatingfunctionology, Academic Press. 3rd edition 2006.
• B Bollobás, Graph Theory, an introductory course, (Graduate Texts in Mathematics 63) Springer 1979.
• D Jungnickel, Networks and Algorithms, (Algorithms and Computation in Mathematics 5) Springer 1998.

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: take home test in week 8; weighting 20%

End of semester examination: two hours weighting 80%

to the top

Arrangements