Math 40210 - Basic Combinatorics

Fall 2012

Instructor: David Galvin

HOMEWORK

QUIZZES

EXAMS

SUPPLEMENTAL MATERIAL

FEEDBACK

Final: Monday December 10, 4.15pm-6.15pm, Pasquerilla 105

Arrangements and information here

General course arrangements (including information about the textbook) are detailed here.

For grades, please log on to Concourse.

In case you haven't yet had a chance to pick up a copy of the textbook, here is a copy of the first 30 pages or so.

Mathematical preparation: We will make much use of the basic mathematical language of sets and functions, and the techniques of induction and recursion. If you have taken a course such as Math 20630 (Introduction to Reasoning), you will already be fully familiar with everything we will use. If not, then you will be able to pick it up as the semester progresses. Here are some resources that you might find helpful.

Chapter 1 of Matousek and Nesetril's book Invitation to Discrete Mathematics, which gives a very leisurely introduction both to the problems of discrete mathematics and to the basic language and techniques that the subject uses; it also has some great exercises.
A powerpoint presentation from the BYU Math Lab, giving an overview (with lots of examples) of the sort of proof methods that we will frequently use.

I can also recommend Appendix A of the book Introduction to Graph Theory by West (Pearson Prentice Hall), which does the same thing as Chapter 1 of the Matousek and Nesetril book, in a more formal way. You could also look at the book How to prove it by Velleman, which gives a very thorough treatment of fundamental proof techniques.

Here is a document gathering together in one place all relevant graph definitions (it may evolve slightly as the semester progresses).

Supplemental course material:

Here are the slides on the Gale-Shapley algorithm from Lecture 40.

Here are the notes on Catalan numbers from Lecture 37.

Here is an extract from Richard Stanley's book Enumerative Combinatorics in which he lists 66 different interpretations of the Catalan numbers. Here is an addendum to the list, in which he adds 136 more!

Here is a Tower of Hanoi applet.

Here are the notes on generating functions from Lecture 35.

Here are the slides on inclusion-exclusion from Lecture 31.

Here are the slides on Pascal's triangle from Lecture 26.

Here are the slides on basic counting problems from Lecture 25.

Here are the slides on theorems equivalent to the Konig-Egervary theorem from Lecture 24.

Here are the three matching problems from Lecture 19.

Here are the slides giving a brief history of the 4-color problem from Lecture 18.

Here are the three coloring problems from Lecture 16.

Here are the slides on the P versus NP problem from Lecture 12. Here's a link to the trailer for a (possibly very bad) 2012 movie about P versus NP.

Here is a page with information about Hamilton's Icosian game. Here's the Wikipedia page on the problem of the knight's tour.

Here is a link to information about Euler's paper on the Bridges of Konigsberg problem, from Lecture 10.

Here are the slides on Prufer codes from Lecture 9.

Here are the trees from Lecture 5.

Here is Wolfram's page on the Petersen graph, and here is the applet that allows you to move the vertices of the graph around. (From Lecture 4)

Here are the pictures from Lecture 1.

Homework:

Ninth assignment, due in class on Wednesday December 5. Solutions are here.

Eighth assignment, due in class on Friday November 16. Graded questions (all 2pts): 1.8.1 3, 1.8.2 5, 2.4 5, 2.5 6, 2.5 10a. Solutions are here.

Seventh assignment, due in class on Friday November 2. Graded questions: 2.1 7 (2pts), 2.1 11 (2pts), 2.2 4 (2pts), 2.2 7d (2pts), 2.3 5 (2pts). Solutions are here.

Sixth assignment, due in class on Friday October 26. (Modified October 17, to remove questions from Chapter 2, and again on October 23, to remove 1.7.4 (2).) Graded questions: 1.7.1 2 (4pts), 1.7.2 4 (2pts), 1.7.3 3 (3pts), 1.7.4 7 (4pts). Solutions are here, with the accompanying figures page here.

Fifth assignment, due in class on Friday October 5. Graded questions: 1.4.2 4 (3pts), 1.4.2 7a (3pts), 1.5.2 1 (2pts), 1.5.2 6 (3pts), 1.5.2 9 (2pts), 1.6.1 1 a and d (2pts each), 1.6.2 1 (2pts), 1.6.2 8 a and b (2pts each), 1.6.3 2 (2pts). Solutions are here, with the accompanying figures page here.

Fourth assignment, due in class on Monday September 24. Graded questions: 1.4.2 4 (3pts), 1.4.2 7a (3pts), 1.4.3 1 (2pts), P versus NP 1 (3pts), 1.5.1 4 (3pts), 1.5.1 8 (2pts). Solutions are here, with the accompanying figures page here.

Third assignment, due in class on Monday September 17. (NB: modified September 12; questions on Section 1.4.2 moved to next homework). Graded questions: 1.3.3 1 (2pts), 1.3.3 2 (3pts), 1.3.4 2a (1pt), 1.3.4 3 (2pts), 1.3.4 4 (2pts), 1.3.4 7 (3pts). Solutions are here.

Second assignment, due in class on Friday September 7. Graded questions: 1.2.1 8d (3pts), 1.2.2 3 (2pts), 1.2.2 4a (2pts), 1.2.2 5 (2pts), 1.3.2 2 (2pts), 1.3.2 9 (3pts). Solutions are here.

First assignment, due in class on Friday August 31. NB: This homework has been modified. Problems 8 d) and 11 a) from Section 1.2.1 have been moved to homework 2. Graded questions: 1.1.1. 1 (2pts), 1.1.2 1 (2pts), 1.1.2 2 (3pts), 1.1.2 10 (3pts), 1.1.3 10 (2pts), Extra Problem 2 (3pts). Solutions are here, with the accompanying figures page here.

Quizzes:

Fifth quiz, with solutions.

Fourth quiz, with solutions.

Third quiz, with solutions.

Second quiz, with solutions.

First quiz, with solutions.

Exams:

Here's general information, including office hours and some review questions, for the final exam.

Here's general information, including office hours for the first exam. The exam, with solutions, is here