Math 4707: Introduction to combinatorics and graph theory (Spring 2022)
Lectures: Mondays and Wednesdays 2:30-4:25 in Vincent Hall 211.
Instructor: Gregg Musiker (musiker "at" math.umn.edu)
Office Hours: Tuesdays 1:10-2:00 and Fridays 2:30-3:20 In Vincent Hall 251 (or via Zoom); also by appointment.
Prerequisites:
Math 2243 and either Math 2283 or 3283 (or their equivalent). Students will be expected to know some calculus and linear algebra,
as well as having some familiarity with proof techniques, such as mathematical induction.
Required text:
Discrete Mathematics: elementary and beyond, by Lovasz, Pelikan, and Vesztergombi
(2003, Springer-Verlag).
Homework (40%): There will be 6 homework assignments due approximately every other week (tentatively) on Wednesdays. The first homework assignment is due on Wednesday Feb 2nd.
I encourage collaboration on the homework, as long as each person understands the solutions, writes them up in their own words, and indicates on the homework page their collaborators. Late homework will not be accepted. Early homework is fine, and can be left in my mailbox in the School of Math mailroom in Vincent Hall 107. Homework solutions should be well-explained-- the grader is told not to give credit for an unsupported answer. Complaints about the grading should be brought to me.
Three Exams (20% each): There will be 3 in-class exams, dates are listed below, each of which will be open book, open notes, and with calculators allowed. 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.
(Jan 19) Lecture 1: Introduction to the Course and Enumeration (Chapter 1 of LPV, Secs 1.1-1.3)
(Jan 24 ) Lecture 2: Enumeration (Chapter 1 of LPV, Secs 1.4-1.8)
(Jan 26) Lecture 3: Induction and the Pigeon-hole Principle (Chapter 2 of LPV, Secs 2.1, 2.4)
(Jan 31) Lecture 4: Inclusion-Exclusion and Asymptotics (Chapter 2 of LPV, Secs 2.2-2.3, 2.5 )
(Feb 2) Lecture 5: The Binomial Theorem, more Identities in Pascal's Triangle, and choosing Multisets (Chapter 3 of LPV, Secs 3.1-3.6)
Instructor: Gregg Musiker (musiker "at" math.umn.edu)
Office Hours: Tuesdays 1:10-2:00 and Fridays 2:30-3:20 In Vincent Hall 251 (or via Zoom); also by appointment.
Course Description:
This is a course in discrete mathematics, emphasizing both techniques of enumeration (as in Math 5705) as well as graph theory and optimization (as in Math 5707), but with somewhat less depth than in either of Math 5705 or 5707. We plan to cover most of the required text, skipping Chapters 6, 14, and 15. We will also likely supplement the text with some outside material.Prerequisites:
Title | Author(s), Publ. info | Location |
---|---|---|
Invitation to Discrete Mathematics | Matousek and Nesetril, Oxford 1998 | On reserve in math library |
Applied combinatorics | A. Tucker, Wiley & Sons 2004 | On reserve in math library |
Introduction to graph theory | D. West, Prentice Hall 1996 | On reserve in math library |
Grading:
I encourage collaboration on the homework, as long as each person understands the solutions, writes them up in their own words, and indicates on the homework page their collaborators. Late homework will not be accepted. Early homework is fine, and can be left in my mailbox in the School of Math mailroom in Vincent Hall 107. Homework solutions should be well-explained-- the grader is told not to give credit for an unsupported answer. Complaints about the grading should be brought to me.
Class Participation
Participation in class is encouraged. Please feel free to stop me and ask questions during lecture. Otherwise, I might stop and ask you questions instead. Additionally, some course material will be taught by having the students work together in small groups cooperatively, followed by a representative coming to the board to explain their group's answer.Course Syllabus and Tentative Lecture Schedule
Assignment or Exam | Due date | Problems from Lovasz-Pelikan-Vesztergombi text, unless otherwise specified |
---|---|---|
Homework 1 | Wednesday Feb 2 | |
Homework 2 | Wednesday Feb 16 | |
Exam 1 | Monday Feb 21 | |
Homework 3 | Wednesday Mar 2 | |
Homework 4 | Wednesday Mar 23 | |
Exam 2 | Monday Mar 28 | |
Homework 5 | Wednesday April 13 | |
Homework 6 | Wednesday April 27 | |
Exam 3 | Monday May 2 | |