Course Title: DISCRETE MATHEMATICS
Level: Graduate Course
Type: Elective
No. of Credits: 4
Pre-requisites: None
Course Rationale
The goal of this course is to familiarize the student with the, principles and methods of combinatorial analysis and its applications. Students in this course will be exposed to counting methods of Discrete Mathematics utilized to solve a wide variety of practical problems. It should be noted that this course will benefit not only the students enrolled in the Master of Science in Mathematics program, but also students of sciences and engineering seeking to apply the major results derived from the study of discrete mathematics at the undergraduate level. For this reason, such a course should be included as an elective graduate level course offered by the Department of Mathematics and Statistics.
Generating functions are a useful tool in solving enumeration problems. This elective course will provide the opportunity for students interested in utilizing generating functions for the enumeration of important families of graphs such as rooted and unrooted trees. The proof of the Four Colour Theorem, one of the most publicized breakthroughs in mathematics in the last 50 years, will also be covered. Students who take this course will be exposed to the basic ideas behind the proof of this important theorem.
Course Description
The term “discrete” is commonly utilized to signify all topics in mathematics that do “not involve calculus”. While such a fixed viewpoint is both limited and not completely accurate, it can serve as a rough description of this particular course. This course will serve to introduce a number of advanced topics in Discrete Mathematics. We develop closed formulae for various interesting problems of enumerative combinatorics.
In this course, the principles of basic Combinatorics, Graph Theory and Algebra will be developed to the more general setting of enumerative Combinatorics and Graph Theory. Students will be introduced to the notion of combinatorial identities via an exquisite blend of multinomial expansions, generating functions and recurrence relations. They will have the opportunity to utilize the Principle of Inclusion and Exclusion as well as their associated inversion formulas. More advanced properties and applications of counting numbers such as Stirling, Bell, Fibonacci and Catalan sequences will be discussed. Particular attention will be paid to the recurrence relations involved in counting systems. Generating functions will be utilized to solve the more significant graphical enumeration problems. Important results such as the enumeration of rooted and unrooted trees will be derived. A few important topics in Graph Theory that are not covered in the undergraduate course MATH 3400 (Graph Theory) will also be explored. Tutte’s Theorem in planarity and the more recent developments by Thomassen leading to a proof of Kuratowski’s Theorem will be incorporated. Fundamental ideas, such as the use of Kempe chains (used in proving the Four Colour Theorem) will also be introduced.
Learning Outcomes
Upon successful completion of the course, students will be able to:
- Utilize the multinomial theorem to form combinatorial identities.
- Illustrate various properties of advanced counting numbers.
- Identify and utilize the principle of inclusion and exclusion.
- Apply generating functions to solve various enumeration problems in Combinatorics and Graph Theory.
- Discuss the main ideas in the proofs of important results in Graph Theory such as Kuratowski’s Theorem and the Four Colour Theorem.
- Use Combinatorial and Graph Theory ideas for the development of algorithms to solve applied problems.
Content (48 hours)
- Combinatorial Identities: (4 hours)
- Principle of Inclusion and Exclusion: (4 hours)
- Stirling, Bell, Fibonacci and Catalan numbers: (4 hours)
- Combinatorial Enumeration: (12 hours)
- Graphical Enumeration: Enumeration of Rooted Trees: results of Cayley and Polya. Enumeration of unrooted trees, both central and bicentral: Otter’s Formula. (12 hours)
- Important topics in Graph Theory: Proof of Tutte’s Theorem. Lemmae and Theorems of Thomassen. Proof of Kuratowski’s Theorem. Basic ideas in proof of the Four Colour Theorem: Kempe’s Chain’s etc.(12 hours)
Teaching Methodology
Lectures: Three (3) lectures each week (50 minutes each).
Tutorials: One (1) weekly tutorial session (50 minutes of problem solving, based on theory covered during lectures).
Assessment
Coursework Mark: 40%
- Two 12% Coursework examinations based on the theory covered during the semester and the assignments given.
- 16% Assignments - based on eight 2% problem papers given during the semester. The solutions to these assignments will be discussed at tutorials after the submission dates have passed.
Final Examination: 60% (one 3-hour written paper)
Course Calendar
Week |
Lecture/Tutorial Topic |
Assignments |
---|---|---|
1 |
Combinatorial Identities |
Assignment #1 |
2 |
The Principle of Inclusion and Exclusion |
Assignment #2 |
3 |
Stirling, Bell, Fibonacci and Catalan Numbers |
Assignment#3 |
4 |
Combinatorial Enumeration |
Assignment #4 |
5 |
Combinatorial Enumeration |
Coursework Exam #1 |
6 |
Combinatorial Enumeration |
- |
7 |
Trees, tree coding and generation of codes |
Assignment#5 |
8 |
Enumeration of Rooted trees: results of Cayley and Polya |
Assignment #6 |
9 |
Enumeration of Unrooted trees: Otter’s formula |
Assignment#7 |
10 |
Tutte’s Theorem and Planarity |
- |
11 |
Thomassen’s and Kuratowski’s Theorems |
Coursework Exam#2 |
12 |
Topics from the Four Colour Theorem |
Assignment#8 |
13 |
Revision |
- |
Suggested Texts / References
Text Book:
- J. Riordan, An Introduction to Combinatorial Analysis, Princeton University Press, ISBN 0-691-02365-4, 1978.
Reference Books:
- B.Bollobas, Modern Graph Theory, Springer, Corrected Edition 1998,ISBN-13:978-0387984889.
- J.A.Bondy ,U.S.R.Murthy, Graph Theory ,Springer, 2008,,ISBN -13:978-1846289699.
- M.Aigner,A Course in Enumeration(Graduate Texts in Mathematics)Springer 2007,ISBN -13:978-3540390329.