Here are the problems for the Les Diablerets minicourse.
Right now I am teaching MAT332: Introduction to Graph Theory. The syllabus is here
Sometimes I teach linear algebra, and google analytics tells me that a handout that I made explaining abstract vector spaces is popular, so I'll keep the link up: What is a Vector Space?
Homework
- Homework 1: Due Sept 27
- Homework 2: Due Oct 11
- Homework 3: Due Oct 27
- Homework 4: Due Nov 10
- Homework 5: Due Nov 29
- Homework 6: Due Dec 6
Schedule
- Tu. Sept 13
- Topic: Introduction to Graphs.
- Resources: West Ch. 1.1, Appendix A.
- Handout
- Th. Sept 15
- Topic: Eulerian Circuits.
- Resources: West Ch. 1.2, Bona Ch. 9.
- Tu. Sept 20
- Topic: Hamiltonian Cycles and Tournaments.
- Resources: Bona Ch. 9.
- Handout
- Th. Sept 22
- Topic: Trees.
- Resources: West Ch. 2.1.
- Tu. Sept 27
- Topic: Spanning Tree Algorithms.
- Resources: West Ch. 2.3.
- Th. Sept 29
- Topic: Counting Spanning Trees.
- Resources: West Ch. 2.2.
- Tu. Oct 4
- Topic: Matchings, Konig's theorem and Hall's theorem.
- Resources: Diestel Ch. 2.1.
- Notes on Latin Squares
- Th. Oct 6
- Topic: Consequences of Hall's theorem, Gale-Shapley algorithm.
- Resources: Diestel Ch. 2.1, West Ch. 3.2.
- Tu. Oct 11
- Topic: Examples of Gale-Shapley, Tutte's Theorem.
- Resources: West Ch. 3.3. (West uses the term ``1-factor'' instead of ``perfect matching''. See remark 3.3.2 for the technical distinction)
- Th. Oct 13
- Topic: Consequences of Tutte's theorem, Introduction to connectivity.
- Resources: West Ch. 3.3, West Ch. 4.1
- Midterm topic list
- Tu. Oct 18
- Topic: Connectivity and edge connectivity. Internally disjoint paths.
- Resources: West Ch. 4.1, West Ch. 4.2
- Th. Oct 20
- Topic: Midterm review.
- Tu. Oct 25
- Topic: Midterm.
- Solutions
- Th. Oct 27
- Topic: Menger Theorem
- Resources: West Ch. 4.2
- Tu. Nov 1
- Topic: Edge Menger Theorem, Network Flows
- Resources: West Ch. 4.2, 4.3
- Th. Nov 3
- Topic: Ford Fulkerson Algorithm, Min-Cut Max-Flow
- Resources: West Ch. 4.3
- Tu. Nov 8
- Fall break -- no classes
- Th. Nov 10
- Topic: Applications of Ford-Fulkerson
- Resources: West Ch. 4.3
- Tu. Nov 15
- Topic: Introduction to Vertex Coloring
- Resources: West Ch. 5.1
- Th. Nov 17
- Topic: Chromatic Polynomial
- Resources: West Ch. 5.3
- Tu. Nov 22
- Topic: Chromatic Polynomial (continued), Edge Coloring, Ramsey Theory
- Resources: West Ch. 5.3, 7.1, 8.3
- Th. Nov 24
- Topic: Ramsey's Theorem, introduction to planarity
- Resources: West Thm 8.3.1.1 (to convert West's notation to our own, replace "p-clique" and "independent q-set" with "red K_p" and "blue K_q", respectively, in this proof)
- Tu. Nov 29
- Topic: Euler's Formula, Kuratowski's Theorem, Art Gallery Theorem
- Resources: West Ch. 6.1, 6.2
- Th. Dec 1
- Topic: Google PageRank (not on final exam)
- Resources:
- Tu. Dec 6
- Topic: Review
- Resources: List of topics