Notes from the 2011 Canada/USA Mathcamp:
Introduction to Graph Theory:
- Lecture 1: An introduction to graph theory.
- Lecture 2: A menagerie of graphs.
- Lecture 3: Trees.
- Lecture 4: The chromatic number of a graph.
- Lecture 5: Ramsey theory.
- Lecture 6: Snarks!
- Homework sets: 1, 2, 3, 4, 5.
Perfect Graphs:
- Lecture 1: Why χ(G) is not a local property.
- Lecture 2: An introduction to perfect graphs.
- Lecture 3: Chordal graphs.
- Lecture 4: The perfect graph theorem, part 1/2.
- Lecture 5: The perfect graph theorem, part 2/2.
- Homework sets: 1, 2, 3, 4, 5.
- Marshall's beautiful solution to the last problem on the first HW set. (The original version had you start with C6, which required you to draw about 5000 vertices to complete the problem :/) Oh, and guess what language he used to draw it...
Flows on Graphs:
- Lecture 1: The Max-Flow Min-Cut theorem.
- Lecture 2: Applications of Max-Flow Min-Cut: Hall, Menger, Dilworth.
- Lecture 3: Flows and Tournaments.
- Lecture 4: Algebraic flows.
- Homework sets: 1, 2, 3, 4, 5.
Spectral Graph Theory:
- Lecture 1: An introduction to spectral theory.
- Lecture 2: Eigenvalues and their uses.
- Lecture 3: Relating eigenvalues to graph-theoretic properties.
- Lecture 4: The spectrum and the chromatic number.
- Lecture 5: The matrix-tree theorem.
- Lecture 6: Spectral theory and decomposition problems, day 1/2.
- Lecture 7: Spectral theory and decomposition problems, day 2/2.
- Lecture 8: Strongly regular graphs and the friendship theorem, day 1/2.
- Lecture 9: Strongly regular graphs and the friendship theorem, day 2/2.
- Lecture 10: Applications: Google's PageRank algorithm, and fullerenes.
- Homework sets: 1, 2, 3, 4, 5, 6, 7, 8, 9.
Electrical Networks and Piffles:
- Lecture 1: Electrical networks and piffles, day 1/2.
- Lecture 2: Electrical networks and piffles, day 2/2.
- Homework sets: 1.
Martin's Axiom:
- Lecture 1: Dominating functions and the failure of the continuum hypothesis.
- Lecture 2: Martin's axiom and dominating functions.
- Homework sets: 1.
Many Campers Sort Piles:
- Lecture 1: Many campers sort piles!