Math 443/543, Fall 2012
Instructor: David Glickenstein
Office: Mathematics 715
Office Phone: 621-2463
Office Hours: Monday 3-4 (Math 715), Wednesday 10-11 (Math 715),
Thursday 1:30-2:30 (Math 220)
Email: glickenstein@math.arizona.edu
Handouts
Exams
- Exam 1 will be in class on October 8. It will cover
Introduction to graphs, Transportation problems, Planar graphs
and coloroings, and digraphs, traffic, and tournaments. (First
through Fifth batches of notes). You may use one sheet of notes.
Here is an old test 1 (not
guaranteed to be representative of the exam).
- Exam 2 will be in class on November 28. It will cover graphs
as matrices and page rank, graph laplacians, matching and stable
marriage, and small world phenomena (Sixth through Ninth batches
of notes). Here is an old test 2
(not guaranteed to be representative of the exam).
- Final Exam will be December 7, 1-3pm. It will cover all
topics, including network flows. Here is an old final exam (not guaranteed to be
representative of the exam).
- Office hours for the last week of class will be Thursday
3-4:30 and Friday 10-11:30.
Notes and Readings
C-x refers to Chapter x in Chartrand, BM-x refers to Chapter x in
Bondy-Murty, etc.
- First batch: Introduction to graphs
- Readings: C-1.3, BM 1.1 Definitions and Examples, C-2.1,
C-2.2, C-2.3, C-2.4
- Second batch: Transportation Problems
- Readings: C-3, BM 18.1, 18.3 (part on Closure of a Graph)
- Third batch: Planar graphs and colorings
- Readings: C-9.1, BM-10.1, 10.3, 10.5, C-9.2, 9.3, BM-11
- Fourth batch: Connector Problems
- Fifth batch: Digraphs, traffic, and
tournaments - updated 9/28
- Sixth batch: Graphs as Matrices and
PageRank
- Seventh batch: Graph Laplacians -
updated 11/5
- Eighth batch: Matching and Stable
Marriage - updated 10/29
- Ninth batch: Small World Phenomena-
updated 11/7
- Tenth batch: Network flows - updated
12/5
Textbook and Supplementary material
- C. Introductory Graph Theory, by Gary Chartrand, published by
Dover.
- BM. Graph Theory, by J.A. Bondy and U.S.R. Murty, available as
an ebook through UA here.
- BL. The $25,000,000,000 Eigenvector:
The Linear Algebra Behind Google by K. Bryan and T. Leise.
- 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.
- M. Mathematics
for Computer Science by Albert Meyer.
- WS. Collective
dynamics
of `small-world' networks, by Duncan Watts and Steven
Strogatz, published in Nature (you need UA access to get this
paper).
- Website from previous time I taught this class: http://math.arizona.edu/~glickenstein/math443f08.
Homework (to be done)
- C-1, problems 21, 22
- 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 1, 2, 3, 5, 6, 7, 10, 14,15, 16, 18
- C-2, problems 36,40,43,45,46,53,57.
- C-3, problems 1, 2, 7, 17, 18, 23, 24
- BM- 18.1.1
- C-9, problems 2, 3, 8, 9, 15, 21, 24, 25, 27
- BM- 10.1.7
- C-4, problems 4, 6, 7, 12, 13, 14, 18
- C-7, problems 4, 7, 8, 9, 11, 13, 17, 19, 20 (see p. 156 for
definition of transmitter and receiver)
- C-10.1 - read about "incidence matrices" on p. 220. Do
problems 2, 4, 7, 9
- BL-Exercises 1, 3, 5
- BL - Exercises 7,8,9,10,11
- Problem sheet 1 - updated 11/16
- C-5, 20, 24, 27
- Problem sheet 2 on stable marriage.
- Problem sheet 3 on small world. -
updated 11/19
- Problem sheet 4 on network flows
- BM - 7.1.2, 7.1.3
Homework assignments (to be turned in)
- Due Wednesday, September 5: C-2 problems 3, 15, 18, Induction
Problem listed above.
- Due Wednesday, September 19: C-2 problem 53, C-3 problems 7,
23
- Due Wednesday, October 3: C-9 problems 8, 25, Read the
definition of dual of a plane graph in BM on p. 252, then do
10.3.8a (note that e(G) denotes the number of edges and v(G)
denotes the number of vertices).
- Due Wednesday October 24: C-10.1 problem 7, BL- Exercises 1,5
- Due Wednesday November 7: Problem Sheet 1- problems 1, 6, 7, 8
- Due Monday November 26: Problem Sheet 2 - problems 1, 3
,Problem Sheet 3 - problems 6a, 7 (you may use the result from
problem 5 if needed).
Grad Student Presentations
- Sankar Veeramoni - "Max Differential Coloring," Friday,
November 14
- Mohammad Jawaherul Alam - "Canonical Orders, Schnyder
Realizers and Their Applications in Contact Representations,"
Friday, November 14
- Vida Ravanmehr - "Applications of graph theory in coding
theory (1)," Monday, November 17
- Sayed Mehrdad Khatami - "Applications of graph theory in
coding theory (2)," Monday, November 17
- Mohammad Abdel Rahman - "TBA," Monday, December 3
- Richard Russell - "TBA," Monday, December 3
- Hanif Rahbari - "TBA," Wednesday, December 5
glickenstein@math.arizona.edu
Last updated December 5, 2012