Math 443/543, Fall 2014
Instructor: David Glickenstein
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)
Handouts
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
- 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)
- Sixth batch: Stable
marriage (latex)
- Seventh batch: small world
(latex) Updated 11/21
- Readings: WS, EK Chapter 20, K
- Eighth batch: Network flows
(latex)
Textbook and Supplementary material
- 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/
Homework
- 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)
To turn in
- 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
Presentations (543 students)
Last updated December 11, 2014