MAD 4203 Combinatorics and Graph Theory I

This is the format this course currently has.

Course Information

 

Text: Fred S. Roberts, Applied Combinatorics

 

Prerequisite:

One year of calculus; some introductory probability. Or consent of instructor. Or be breathing.

Grading:

60% Weekly homework

10% One "research" problem OR a report on a paper in the literature.

 

Research problem

Most of the suggested problems are not difficult, but the type thinking involved seems to work best if you're not under pressure. Thus, I suggest you plan to work on the problem at a leisurely pace over a period of several weeks. I encourage you to work on it awhile, and, if you get stuck, come in for a hint. Then you should repeat this process in an iterative manner until you're done. The final document is to be a well written technical report in which you first describe the problem, then give your solution to it along with any illustrative examples, and finally state some conclusions or thoughts about additional work which might be carried out. Your grade will depend on both technical content and excellence of presentation.

 

Paper in the literature

You are to rewrite the paper in your own words. The work is to be rigorous mathematically, and all gaps in the original paper are to be filled. It is a good idea to make up examples illustrating the points, even if no such examples are in the original paper. Figures also are helpful. If the paper already includes examples and figures, try to find different ones for your report. Your grade will depend not only on technical accuracy, but also on the clarity and ease of understanding of your presentation. Full reference is to be given to any work mentioned, including the paper you are rewriting. You do not have to derive results mentioned which come from other papers-just give a reference to the other work and state the result from it which is being used. Please hand in a copy of the original paper along with your rewrite.

 

Whichever you choose

Before you start work, indicate to me which research project or paper you wish to do (first come gets first choice). Everyone must do a different one. Report is due November 19, 1998.

 

10% Short quizzes each Thursday on ungraded problems.

20% Comprehensive in class open book and open notes final examination.

Subjects to be covered

 

Chapter 1 Introduction

Chapter 2 Counting rules (sketchily, most will be covered as needed)

Chapter 3 Introduction to graph theory

Chapter 4 Generating functions for combinatorial objects

Chapter 5 Recurrence relations

Chapter 6 The principle of inclusion and exclusion

Section 8.1 The pigeonhole principle

Chapter 11 Some more graph theory (path problems)

Chapter 12 Still more graph theory (matching and covering)

 

Return to my home page