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.