MAD 5205-Combinatorics and Graph Theory II

This is the format of this course as it was offered in Spring Semester, 1998

Text: There is no text. References to several appropriate books will be given as the course progresses.

Prerequisite: MAD 4203 or equivalent, or permission of instructor.

Grading:

65% Homework, assigned and due weekly. You are encouraged to work in groups to solve the homework problems. However, you are to write up results individually and in your own words.


15% A special project of some sort. There are three possibilities. Each is broken down into a "proposal" in which you describe what you intend to do (worth 3% and should be one or two pages at most) and a final report where you tell what you have done (worth 12% and will be as long as it takes to do a good job). All proposals and reports are to be in good English and demonstrate clear understanding of the subject. Grades will be based on presentation techniques as well as the technical content. Proposals will be due February 18, 1998 with the final report due the last week of class (or earlier if you'd like me to be smiling while I grade). It is recognized that you are all at different levels of familiarity with the subject and you should feel free to enlist my aid when you run into problems. I'll help if I can. You are to decide on one of the following.


• Rewrite of a paper in the literature. You are to find a relevant paper in the current literature, published within the last two years, on which you would like to report. This paper must be approved by me before you write your proposal. It is expected that you will select a paper based on its interest to you, and not on its brevity. The proposal will outline why that particular paper caught your attention. Then, for the final report, you are to rewrite the paper in your own words, filling in all gaps. Your work must be rigorous mathematically. Full reference is to be given to any work mentioned, including the paper you are rewriting. Make up examples if they will help to explain the paper. Try not to use the same examples as are in the original paper. In sentences do not use abbreviations such as "iff" or symbols such as a backward "E" as substitutes for English phrases which should be spelled out. You do not have to derive results used in your paper which are taken from other papers; just state such results clearly and reference the source completely. A copy of the original paper is to be included with your rewrite. Please reread this paragraph before starting your report.
  
• Preparation of a comprehensive review of one area of combinatorics or graph theory. The proposal will describe briefly the area you have selected, give some indication of why it is of interest to you, and indicate how you will approach finding the necessary material. Check out the subject with me before you prepare the proposal. The final report will, of course, then present your findings in a clear manner with appropriate use of examples and figures.
  
• Carrying out a "mini" research project. The proposal will outline the area in which you want to find some results, why you are interested in it, any specific goals, and why you think you can accomplish the goals in the given time frame. Again, check it out with me before you prepare your proposal. The final report will be a complete technical report with a description of your problem, its solution, conclusions, indications of possible future work, and references. The subject of this research is not to be related to your dissertation or any other research in which you are involved.
  

20% Comprehensive final examination

Subjects to be covered: The subjects which I plan to cover are those which I have found helpful in my own work, which are uniformly considered to be important, or which I think have application in computer science or other disciplines, as well as mathematics.
Combinatorics: Polya's counting theory; block designs, Latin squares and finite projective planes; coding theory.
Graph Theory: Network flows (max flow/min cut theorem), invariants and extremal graph theory, probabalistic methods in graph theory, hypergraphs, matroids with a graph theoretic emphasis (if time permits).

Return to my home page