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% |
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] | 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
- understand your solutions,
- write your solutions in your own words without copying, and
- indicate the names of your collaborators.
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.
Last Modified 2013.12.20.
The views and opinions expressed in this page are strictly those of the page author.
The contents of this page have not been reviewed or approved by the University of Minnesota.
Sat and forever am at work here.
The views and opinions expressed in this page are strictly those of the page author.
The contents of this page have not been reviewed or approved by the University of Minnesota.
Sat and forever am at work here.