Math 443/543, Fall 2008
Instructor: David Glickenstein
Office: Mathematics 715
Office Phone: 621-2463
Office Hours: TBA
Office hours exam week
Exam week I will have office hours :
- Thursday, December 11, 2-4 PM in Math 715.
- Friday, December 12, 10-12 AM in Math 715
- Exam 1 will be in class on October 8
- It will cover material through tournaments. REMEMBER THAT
30-50% OF THE EXAM COMES EXACTLY OUT OF HOMEWORK PROBLEMS, PROBABLY
ONES WHICH WERE NEVER REQUIRED TO BE TURNED IN.
- Exam 2 will be in class on December 3. It will cover everything
from pipeline problems trhough stable marriage.
- Final Exam will be Friday, Dec 12, 2-4pm. It will be
comprehensive.YOU MAY USE YOUR NOTES FOR THE EXAM.
Textbook and Supplementary material
- C. Introductory Graph Theory, by Gary Chartrand, published by
- BM. Graph Theory and Applications, by J.A. Bondy and U.S.R.
- T. Extra material on the Four Color Theorem: Paper by Robin Thomas
- BL. The $25,000,000,000 Eigenvector:
Linear Algebra Behind Google by K. Bryan and T. Leise.
- M. Notes
on Stable Marriage Problem, by Albert R. Meyer from MIT. You can
ignore the first part on state machines.
- EK. Notes
on Small World Phenomena, by David Easley and Jon Kleinberg from
- K. The
Small World Phenomenon: An Algorithmic Perspective, by Jon
- WS. Collective
dynamics of `small-world' networks, by Duncan Watts and Steven
Strogatz, published in Nature (you need UA access to get this paper).
- H. Lecture
notes on Graph Minors, by Jan van den Heuvel.
- D. Graph theory, by Reinhard Diestel. Electronic edition
We will use some material from Chapter 12.
Homework (to be done)
C-x refers to Chapter x in Chartrand, BM-x refers to Chapter x in
- C-1, problems 21, 22
- C-2, problems 2, 3, 5, 6, 7, 10, 14,15, 16, 18, 24, 25
- Induction Problem: Use mathematical induction to prove that the
sum of an even number of odd numbers is even and an odd number of odd
numbers is odd. (Hint: recall that even numbers can be enumerated as 2n
for n=0,1,... and that odd numbers can be enumerated as 2m+1 for
- C-2, problems 36,40,43,45,46,53,57.
- C-3, problems 1, 2, 7, 17, 18, 23, 24
- BM, problems 1.8.1, 1.8.2, 1.8.3
- C-4, problems 1,2,6,7,9,12,14
- C-9, problems, 1, 2, 3, 6, 8, 11, 12, 19, 20, 21, 23, 25, 26.
- C-10, problems 11, 12, 13, 14, 15, 16
- C-7, problems 3, 7, 8, 11, 13, 17, 19
- Extra problem: Check directly that every tournament of order 4
has a hamiltonian path.
- BM-11, 11.3.2, 11.3.4
- BL-Exercises 1, 3, 5, 9, 10, 11, 12, 14
- C-5, problems 5, 6, 10, 12, 14, 20, 24, 27
- Stable Marriage problems.
- Problems on small world, graph
minors, and Laplacians.
Homework assignments (to be turned in)
- Due Wednesday, Sept 10: C-2 problems 2, 16, Induction Problem
- Due Wednesday, Sept 17, C-2 problem 36, C-3 problems 18, 24.
- Due Wednesday, October 1, BM-1.8 problem 1.8.1, C-4 problem 14,
C-10 problem 12.
- Due Wednesday, October 22, C-7 problem 19, BM-11.3 problem 11.3.2.
- Due Friday, November 7, BL exercises 1,5,10
- Optional homework, due Wednesday, December 10, from problems on
small world, graph minors, and Laplacians, problems 2,3,7
Grad Student Presentations
Here are some of the grad student presentations
Last updated December 10, 2008