Math 443/543, Fall 2008
Instructor: David Glickenstein
Office: Mathematics 715
Office Phone: 621-2463
Office Hours: TBA
Email: glickenstein@math.arizona.edu
Handouts
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
Exams
- 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.
Notes
Textbook and Supplementary material
- C. Introductory Graph Theory, by Gary Chartrand, published by
Dover.
- BM. Graph Theory and Applications, by J.A. Bondy and U.S.R.
Murty,
available here.
- T. Extra material on the Four Color Theorem: Paper by Robin Thomas
- BL. The $25,000,000,000 Eigenvector:
The
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
Cornell.
- K. The
Small World Phenomenon: An Algorithmic Perspective, by Jon
Kleinberg.
- 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
available here.
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
Bondy-Murty
- 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
m=0,1,2,...)
- 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
listed above.
- 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
glickenstein@math.arizona.edu
Last updated December 10, 2008