Math 443/543, Fall 2008

Exam week I will have office hours :

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.

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.

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.

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

Here are some of the grad student presentations

glickenstein@math.arizona.edu
Last updated December 10, 2008