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.

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: 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).

Other useful texts
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:

  • 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.

  • 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

  • (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)

  • Homework assignments (tentative) and exams
    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