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

- 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.

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
- C-4.1, BM-6.3
- Fifth batch: Digraphs, traffic, and tournaments - updated 9/28
- Readings: C-7.1, C-7.2
- Sixth batch: Graphs as Matrices and PageRank
- C-10.1, BL
- Seventh batch: Graph Laplacians - updated 11/5
- Eighth batch: Matching and Stable
Marriage - updated 10/29

- C-5.2, M-9.2
- Ninth batch: Small World Phenomena-
updated 11/7

- EK, K
- Tenth batch: Network flows - updated
12/5

- BM-7

- 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.

- 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

- 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).

- 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