MATH 108: Introduction to Combinatorics

Spring 2021

Time: Mon, Wed, Fri 10:00 – 10:50
Instructor: Matthew Kwan,
Office hours: Wed 14:00 – 15:00 or by appointment
Assistant: Sammy Luo,
Office hours: Fri 16:00 – 17:30

This is a proof-based course in combinatorics and discrete mathematics. We will cover a bit of graph theory, a bit about some other other discrete structures (posets, set systems), and a bit of enumerative combinatorics (i.e. counting). To start with, we will follow these lecture notes by Freddie Manners, though we may end up diverging from the notes later on. There is no required textbook.

The only prerequisite is the core content of MATH 51. These topics relate to many other areas of higher mathematics and computer science and we will touch on these, but without assuming prior knowledge.

We will meet using Zoom and Canvas. You should be able to join via the Zoom link on the sidebar of the course Canvas page (here). It's perfectly fine for you to unmute yourself and interrupt to ask questions. Our meetings will be automatically recorded, and should be available on Canvas (only to enrolled students) shortly afterwards. I apologise in advance for any technical difficulties that may arise!

There will be Zoom meetings for “open” office hours, which will not be recorded. If you have questions you would like to ask privately or if these times are unsuitable for you, please send an email to make an appointment. These policies may change depending on demand.

This year, grades will be entirely determined by homework, which will be posted on this page at the start of every week (or earlier), and should be submitted on Gradescope by 17:00 the following Sunday. I will set up Gradescope to actually accept submissions until a day later, as a grace period in case of last-minute technical difficulties. Also, your lowest homework score will be dropped from consideration.

You are permitted (and encouraged!) to discuss the problems with other students, but you must write up the solutions yourself. Please work out problems neatly — do not hand in your scratch work.

The (tentative) schedule is as follows.

Week 1:  Introduction. Graphs; definition and properties. Edge and vertex coloring.  Homework
Week 2:  Eulerian and Hamiltonian graphs; necessary and/or sufficient conditions. Applications; Gray codes, de Bruijn sequences.  Homework
Week 3:  Bipartite matching. Theorems of Hall and Kőnig. Edge coloring of bipartite graphs.  Homework
Week 4:  Partially (and totally) ordered sets. Theorems of Dilworth and Mirsky. Monotone subsequences.  Homework
Week 5:  Counting and double-counting. Binomial coefficients. Sperner's theorem on the discrete cube.  Homework
Week 6:  More counting. Inclusion-exclusion. Trees.  Homework
Week 7:   Cayley's formula on labelled trees. Counting binary trees, and Catalan numbers.
Week 8:  Derangements. Cycle structure and sign of permutations. Permutations without long cycles. Introduction to generating functions.
Week 9:   Generating functions and examples. Integer partitions and Euler's pentagonal formula.
Week 10: *  Further topics; TBA

* There will be no class on Monday 31 May, due to a public holiday.