Math 4707

Fall 2013

Introduction to Combinatorics and Graph Theory

Basic Information

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

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 5, 6, 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 0387955852.

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.

• Midterm 1, Monday, Oct 07; solutions.
• Midterm 2, Monday, Nov 11; solutions.
• Midterm 3, Wednesday, Dec 11; solutions.

Calendar

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

Month	Monday		Wednesday
September			04	Permutations, sets, sequences (1.1–1.6)
	09	Subsets, induction, estimates (1.7–2.2)	11	Binomial theorem, inclusion-exclusion (notes on derangements courtesy of Dennis White), pigeonholes (2.3–3.1)
	16	Multinomial coefficients, Pascal's triangle (3.2–3.5)	18	Fibonacci numbers (4.1–4.2) Problem Set 1
	23	Generating functions (notes courtesy of Gregg Musiker), linear recurrence (4.3)	25	Generalized binomial theorem
October	30	Catalan numbers (handout)	02	Review Problem Set 2 (solutions posted on Moodle)
	07	Midterm 1 (solutions)	09	Introduction to graph theory (7.1)
	14	Connectivity, Eulerian tours (7.2–7.3)	16	Trees (8.1–8.2)
	21	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.	23	Optimisation on graphs (9.1–9.2) Problem Set 3 (solutions posted on Moodle)
	28	Matchings: Hall's marriage theorem (10.3–10.4)	30	Stable matchings
November	04	k-factors	06	Domino tilings Problem Set 4 (solutions posted on Moodle)
	11	Midterm 2 (solutions)	13	Planar graphs: Euler's formula (12.1) (20 proofs curated by David Eppstein)
	18	Planar graphs and polyhedra (12.2–12.3)	20	Graph colouring (13.2–13.3) (notes on chromatic polynomials courtesy of Dennis White)
	25	Five colour theorem (13.4), Ramsey theory Problem Set 5 (solutions posted on Moodle)	27	Thanksgiving
December	02	Introduction to probability (5.1)	04	Random graphs (lecture notes)
	09	Review Problem Set 6 (solutions posted on Moodle)	11	Midterm 3 (solutions)

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. Refer to the calendar above for tentative due dates.

Problem Set	Due Date	Problems	Optional Exercises
Problem Set 1	Wed, Sep 18	1.8 # 16, 19, 20*, 21, 27, 28, 32 2.5 # 2, 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 2.5 # 1, 3, 5, 7, 8
Problem Set 2	Wed, Oct 02	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.	3.1 # 1 3.2 # 2, 3 3.6 # 3, 4 4.2 # 4, 5 4.3 # 3
Problem Set 3	Wed, Oct 23	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, 9, 10, 11 8.1 # 2 8.2 # 3 8.5 # 3
Problem Set 4	Wed, Nov 06	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	Mon, Nov 25	12.3 # 1, 2, 4+, 6*, 7 + 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
Problem Set 6	Mon, Dec 09	13.4 # 2, 3, 4, 5, 6, 7 5.4 # 2, 3, 4, 5 No more homework =(	13.3 # 2, 4 13.4 # 1, 8, 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

• Sep 23: Students are encouraged to check Moodle to confirm that grades are properly recorded.
• Oct 04: Problem Set 2 solutions to selected problems posted on Moodle.
• Oct 09: Midterm 1 solutions posted.
• Nov 14: Midterm 2 solutions posted.
• Dec 12: Midterm 3 solutions posted.
• Dec 19: Course grade distribution posted, with the letter grade ranges; check your total course score on Moodle.

---