GRAPH THEORY AND COMBINATORICS
Schedule.
Week 1.
Wednesday January 3rd.
Graph Theory: The Art Gallery Problem.
Friday January 5th.
Graph Theory: Introduction; Euler Circuits.
Week 2.
Monday January 8th.
Graph Theory: Hamiltonian Cycles.
Wednesday January 10th.
Graph Theory: Good Characterisations; Bipartite Graphs.
Friday January 12th.
Graph Theory: Matchings; Latin Squares.
[Assignment 1 assigned.]
Week 3.
Monday January 15th.
Graph Theory: Vertex Colouring.
Wednesday January 17th.
Graph Theory: Menger's Theorem;
k
-connectivity.
Friday January 19th.
Graph Theory: MaxFlow-MinCut; a mining example.
Week 4.
Monday January 22nd.
Graph Theory: Connectivity and Hamiltonian Cycles.
Wednesday January 24th.
Graph Theory: Planar Graphs; 5-Colour Theorem.
[Assignment 1 due.]
Friday January 26th.
Graph Theory: List-Colouring.
[Assignment 2 assigned.]
Week 5.
Monday January 29th.
Graph Theory: Graph Minors.
Wednesday January 31st.
Graph Theory: Kuratowski's Theorem.
Friday February 2nd.
Graph Theory: Acyclic Orientations.
Week 6.
Monday February 5th.
Probability: The Interview Problem.
Wednesday February 7th.
Probability: Conditional Probability; the Monty Hall Problem.
[Assignment 2 due.]
Friday February 9th.
Probability: Independence; Expectation.
Week 7.
Monday February 12th.
Probability: The Binomial Distribution; the Birthday Problem.
[Assignment 3 assigned.]
Wednesday February 14th.
Probability: The Crossing Number of Graphs.
Friday February 16th.
Probability: Hashing; Balls and Bins.
Week 8.
Spring Break - No Lectures.
Week 9.
Monday February 26th.
Probability: the Chernoff Bound.
[Assignment 3 due.]
Wednesday February 28th.
MIDTERM EXAM.
Friday March 2nd.
Probability: The Stable Marriage Problem.
[Assignment 4 assigned.]
Week 10.
Monday March 5th.
Probability: Quicksort.
Wednesday March 7th.
Probability: Randomised Minimum-Cut.
Friday March 9th.
Probability: Randomised Minimum-Cut.
Week 11.
Monday March 12th.
The Probabilistic Method: Ramsey Numbers; Stable Sets; Families of Intersecting Sets.
Wednesday March 14th.
The Probabilistic Method: Random Walks.
[Assignment 4 due.]
Friday March 16th.
The Probabilistic Method: Universal Traversal Sequences; Dominating Sets.
[Assignment 5 assigned.]
Week 12.
Monday March 19th.
Combinatorics: Counting Spanning Trees.
Wednesday March 21st.
Combinatorics: Ordinary Generating Functions.
Friday March 23rd.
Combinatorics: Exponential Generating Functions; Derangements.
Week 13.
Monday March 26th.
No Lecture - Election.
Wednesday March 28th.
The Fundamental Theorem of Linear Inequalities.
[Assignment 5 due.]
Friday March 30th.
The Fundamental Theorem of Linear Inequalities.
[Assignment 6 assigned.]
Week 14.
Monday April 2nd.
Combinatorics: Brouwers Fixed Point Theorem.
Wednesday April 4th.
Combinatorics: Graph Counting using Polynomials.
Friday April 6th.
No Lecture - Holiday.
[Assignment 6 due.]
Week 15.
Monday April 9th.
No Lecture - Holiday.
Wednesday April 11th.
The Last Lecture.
Friday April 13th.
FINAL EXAM, 9am.