Office: Mathematics 204

Office Phone: 621-2463

Office Hours: Monday 10:30-11:30 (Math 204), Thursday 1:30-2:30 (Math 220), Friday 2-3 (Math 204)

- Syllabus
- Practice for Exam 1
- Practice for Exam 2
- Final Exam Due Thursday Dec. 18 at 3pm

C-x refers to Chapter x in Chartrand, BM-x refers to Chapter x in
Bondy-Murty, etc.

- First batch: Introduction to graphs
- updated 9/15 (latex)

- Readings: C-1.3, C-2.1, C-2.2, C-2.3, C-2.4
- Second batch: Eulerian and
Hamiltonian graphs - updated 9/15 (latex)

- Readings: C-3.1, 3.2. Supplementary reading: BM1 pp. 54-57
- Third batch: Planar graphs and
coloring problems (latex)
updated 10/10

- Readings: C-9.1, 9.2, 9.3, BM1 - pp. 135-138
- Fourth batch: Connector
problems and shortest path (latex)

- Readings: C-4.1, BM1 - pp. 15-20
- Fifth batch: Graphs as matrices,
spectral graph theory, and PageRank (latex) (updated 11/3)

- Readings: C-10.1, S, BL
- Sixth batch: Stable marriage (latex)
- Readings: M-9.2
- Seventh batch: small world
(latex) Updated 11/21

- Readings: WS, EK Chapter 20, K
- Eighth batch: Network flows (latex)
- Readings: BM-11

- C. Introductory Graph Theory, by Gary Chartrand, published by
Dover.

- D. Graph Theory, by Reinhart Diestel. Free preview here: http://diestel-graph-theory.com/basic.html

- BL. The $25,000,000,000 Eigenvector: The Linear Algebra Behind Google by K. Bryan and T. Leise.
- EK. Networks,
Crowds, and Markets: Reasoning about a Highly Connected World
by David Easley and Jon Kleinberg.

- 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).
- BM1. Graph Theory and Applications, by J.A. Bondy and U.S.R.
Murty. 1976. Some excerpts from this are available on d2l.

- BM2. Graph Theory, by J.A. Bondy and U.S.R. Murty.
- S. Algebraic
Graph Theory, by Richard Stanley. Chapter 9: The Matrix
Tree Theorem. (You should be able to access this when on the UA
network.)

- Website from previous time I taught this class: http://math.arizona.edu/~glickenstein/math443f12.
- Mathematica demonstration of embedding graphs in torus and
Mobius band: http://demonstrations.wolfram.com/EmbeddingsOfGraphsInATorusAndInAMoebiusStrip/

- C-1, problems 17-23
- 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-7, 10, 13, 14,15, 16, 18, 21, 22
- C-2, problems 32,36,37,38, 40,43,44
- C-2, problems 47, 48, 53, 57, 58, 59, 60
- C-3, problems 1, 2, 3, 7, 8, 10-14
- C-3, problems 16, 18-22, 25-29 (28 and 29 actually refer to Example 3.3)
- C-9, problems 2-4, 6, 8, 10, 13
- Problems on Wagner's theorem
- C-9, problems 14-16, 19, 20, 21, 24, 25 (look up
"icosahedron")

- Problems on planar colorings (updated 10/9)
- Worksheet on Economy Trees
- C-4, problems 2, 4, 5, 7-11, 12, 14, 17
- Worksheet on Dijkstra's algorithm
- Quick review of matrices (latex) updated 10/22
- BM1- problems 1.8.1, 1.8.2

- C-10, problems
1-4, 6, 7, 9

- Worksheet on Proof of the Matrix Tree theorem (latex)
- Laplacian problem sheet.

- Worksheet on Introduction to
PageRank (latex)

- Worksheet on Challenges to the PageRank algorithm (latex)
- PageRank problem sheet
- BL-Exercises 1, 3, 5, 7-10, 11, 12

- Worksheet on Stable Marriage (latex)
- Stable marriage problem sheet
- Small world problem sheet (latex)

- Due Tuesday, September 2 by 4pm: C-2 problems 3, 15, 18, Induction Problem listed above.
- Due Wednesday, September 3: Short essay on definition of a
graph and isomorphism (content of C-1.3 and C-2.2). Quiz that
day, too.

- Due Friday, September 5: C-2 problems 22, 32.
- Due Monday, September 8: Short summary of connectedness of a graph, bridges, and cycles (content of C-2.3 and C-2.4). Quiz that day, too.
- Due Friday, September 12: C-2 problems 37, 38, 48
- Due Monday, September 15: Short summary of Eulerian circuits
(C-3.1) and Hamiltonian cycles (C-3.2). Quiz that day, too.

- Due Friday, September 19: C-2 problem 58, C-3 problem 7
- Due Monday, September 22: Write a short essay on closure of a graph and how to use it (BM1 pp. 54-57). Quiz that day, too.
- Due Friday, September 26: C-3 problems 22, 29.
- Due Monday, September 29: Write a short essay on planar graphs and Euler's theorem (C-Theorem 9.1). Quiz that day, too.
- Due Friday, October 3: Problems on Wagner's theorem (corrected 9/28)
- Due Monday,
October 6: Write a short essay on chromatic number (C-9.2).
Quiz that day, too.

- Due Friday, October 10: Problems on higher genus (only these, no need to include problems from previous section in this worksheet).
- Due Monday, October 20: Write a short essay on minimal
spanning trees. Quiz that day, too.

- Due Friday, October 24: C-4 problems 10, 14
- Due Monday, October 26: Write a short essay on shortest paths. Quiz that day.
- Due Friday, October 31: BM1-problem 1.8.1, Read about incidence matrices on C-p. 220 and answer C-10 problem 9 (prove your answer).
- Due Monday, November 3: Write a short essay on the matrix tree theorem. Quiz that day.
- Due Friday, November 7:Proof of the Matrix Tree Theorem worksheet, problems MT2 and MT4, Laplacian problems worksheet #2
- Due Monday,
November 10: Write a short essay on PageRank. Quiz that day,
too.

- Due Friday, November 14: PageRank problem sheet, problem 2, BL-exercise 5.
- Due Monday, November 11: Write a short essay on Stable Marriage. Quiz, too.
- Due Friday, November 21: BL Exercise 11 (you may use a computer program to compute the eigenvectors if you wish). Stable Marriage Problem Sheet 2,4
- Due Monday, November 24: Write a short essay on decentralized search (especially myopic search). Quiz, too.
- Due Monday,
December 1: Small world problem sheet: 4,5

- Nov. 19 - Rashan Eletreby - Graph-based
criteria for spectrum-aware clustering in cognitive radio
networks

- Nov. 19 - Mehdi Golari - Integer programming formulations for minimum spanning forest problem
- Nov. 21 - Elham Sadeghi - Survivable
Network Design with Vertex and Edge Connectivity Constraints

- Nov. 24 - Nicholas Fragiskatos -IMap: Visualizing Network Activity over Internet Maps
- Dec. 5 - Steven Brener
- Dec. 5 - Bahador Saket - Are Crossings Important for Drawing
Large Graphs?

- Dec. 8 - Wessam Afifi - Utilization and fairness in spectrum assignment for opportunistic spectrum access
- Dec. 8 - Sabrina Nusrat