Math 4707

Spring 2016

Introduction to Combinatorics and Graph Theory

Basic Information

• Instructor: Jed Yang,
• Office hours: MW 13:00–14:30 (or by appointment) in Vincent Hall 203B
• Lectures: MW 14:30–16:25 in Vincent Hall 6
• Course website: http://math.umn.edu/~jedyang/4707.16s/

Course Information

This course serves as a gentle introduction to combinatorics, covering topics in both enumeration (Math 5705) and graph theory (Math 5707) but with less depth than the aforementioned courses. Students are expected to know calculus, linear algebra, and have familiarity with proof techniques (e.g., mathematical induction). We plan to cover most of the required text but will skip some chapters (tentatively chapters 6, 11, 14, and 15). We may also supplement the text with outside material.

• Textbook: Discrete mathematics: elementary and beyond, by Lovász, Pelikán, and Vesztergombi, ISBN 9780387955858.

Grading

There will be 3 midterm exams and NO cumulative final exam.
Your grade will be determined by a weighted arithmetic mean of homework and exam scores.
The higher score from the following two schemes will be automatically chosen for each student:

Scheme	Homework	Midterm 1	Midterm 2	Midterm 3
Scheme 1	25%*	25%	25%	25%
Scheme 2	30%	15%	25%	30%

* In Scheme 1, the worst homework score will be dropped.

Examinations

The midterm exams will be administered during regularly scheduled class time. You may use books, notes, and calculators.

Missing an exam is permitted only for the most compelling reasons. You should obtain my permission in advance to miss an exam. Otherwise, you will be given a 0. If you are excused from taking an exam, you will either be given an oral exam or your other exam scores will be prorated.

Tentative exam dates:

• Midterm 1, Monday, Feb 22.
• Midterm 2, Monday, Apr 04.
• Midterm 3, Wednesday, May 04.

Homework

There will be 6 problem sets assigned fortnightly, skipping a week after an exam.

Collaboration is encouraged, as long as you

1. understand your solutions,
2. write your solutions in your own words without copying, and
3. indicate the names of your collaborators.

If you copy work (or collaborate without indicating so), UMN academic dishonesty policies shall be applied.

Late homework will not be accepted; early homework is fine and can be left in my mailbox in the School of Mathematics mailroom near Vincent 105.

Problem sets will be posted on the course website and due at the beginning of lecture on the due dates.

Calendar

To be updated throughout the term; tentative and subject to change.

Month	Monday		Wednesday
January			20	Permutations, sets (1.1, 1.2, 1.6)
	25	Sequences, subsets (1.3, 1.5, 1.7–1.8)	27	Induction, binomial theorem, inclusion-exclusion (2.1, 2.3, 3.1)
February	01	Derangements (notes courtesy of Dennis White), multinomial coefficients (3.2–3.4)	03	Pascal's triangle (3.5–3.6), Fibonacci numbers (4.1–4.2) Problem Set 1
	08	Generating functions (notes courtesy of Gregg Musiker), linear recurrence (4.3), generalized binomial theorem	10	Catalan numbers (handout)
	15	More Catalan numbers, review	17	Review Problem Set 2
	22	Midterm 1	24	Introduction to graphs, connectivity (7.1–7.2)
March	29	Connectivity, Eulerian tours (7.2–7.3)	02	Trees (8.1–8.2)
	07	Trees: Cayley's formula (8.3–8.4) [Expand reference] Two of the four proofs from the book Proofs from THE BOOK (by Aigner and Ziegler) were presented in class. The other two are based on recursion and linear algebra, respectively. Interested students are encouraged to take a look.	09	Unlabelled trees (8.5) Problem Set 3
	14	Spring Break	16	Spring Break
	21	Optimization on graphs (9.1–9.2)	23	Matchings: Hall's marriage theorem (10.3–10.4)
	28	Stable matchings	30	Review Problem Set 4
April	04	Midterm 2	06	Planar graphs: Euler's formula (12.1–12.2) (20 proofs curated by David Eppstein)
	11	Planar graphs and polyhedra (12.3)	13	Graph colouring (13.2–13.3) (notes on chromatic polynomials courtesy of Dennis White)
	18	Five colour theorem (13.4)	20	Ramsey theory, probability (5.1) Problem Set 5
	25	Random graphs (lecture notes)	27	Random graphs
May	02	Review Problem Set 6	04	Midterm 3

Problem Sets

Problem Set	Due Date	Problems	Optional Exercises
Problem Set 1	Wed, Feb 03	1.8 # 16, 19, 20*, 21, 27, 28, 32 2.5 # 1, 4 (a), 6 * Here and elsewhere, please justify your answers.	1.2 # 13, 17, 18 1.8 # 4–7, 26, 29, 33, 34 2.1 # 8, 9, 12 3.1 # 1
Problem Set 2	Wed, Feb 17	3.8 # 6, 8, 9, 11, 12, 13 4.3 # 6*, 9 (a)–(c), 12, 13, 15, 16 * Change "0" to "1" in the problem statement. + Change the first "k+1" to "n+1" in 3.6.4.	3.2 # 2, 3 3.4 # 1, 2 3.6 # 3, 4+ 4.2 # 4, 5 4.3 # 3
Problem Set 3	Wed, Mar 09	7.3 # 5, 9, 11, 12, 13 8.5 # 2, 4, 6, 8*, 9 * You may assume that a number does not appear in both rows in the same column. That is, the graph has no loops.	7.1 # 7 7.2 # 3, 5, 6, 11 8.1 # 2 8.2 # 3 8.5 # 3
Problem Set 4	Wed, Mar 30	9.2 # 3, 4, 6, 8 10.4 # 7*, 8, 9, 13, 14 * The set A should not be the entire left side. That is, it is a nonempty proper subset.	9.1 # 1, 2 9.2 # 2, 5 10.1 # 1, 2 10.4 # 1, 2, 11
Problem Set 5	Wed, Apr 20	12.3 # 1, 2, 4+, 6*, 7 13.4 # 2, 3, 4, 5 + Assume that n is at least 3. * Assume that the faces are regular polygons.	12.1 # 1, 2 12.2 # 1 12.3 # 3=8 13.3 # 2, 4
Problem Set 6	Mon, May 02	13.4 # 6, 7, 8 5.4 # 2, 3, 4, 5 No more homework =(	13.4 # 1, 9 5.2 # 2, 3

Supplementary Media

• The pigeonhole principle demonstrated
• The stable matching algorithm terminates
• Proper drawings of planar graphs
• Colouring maps with four colours

Announcements

• Feb 08: Students are encouraged to check Moodle to confirm that grades are properly recorded.
• Feb 24: Midterm 1 solutions posted; check Moodle for grades.
• Apr 06: Midterm 2 solutions posted; check Moodle for grades.
• Apr 18: The class voted to have the last problem set due on Monday instead of Wednesday to allow time to study for the last midterm.
• May 09: Midterm 3 solutions posted.
• May 09: Course grade distribution posted, with the letter grade ranges; check your total course score on Moodle.

---