Math 4707: Introduction to combinatorics and graph theory (Spring 2013)

Lectures: MW 2:30-4:25 in Vincent Hall 113.

Instructor: Gregg Musiker (musiker "at" math.umn.edu)

Office Hours: (In Vincent Hall 251) Monday 4:25-5:15; Thursday 1:25-2:30; 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 (35%): There will be 6 homework assignments due approximately every other week (tentatively) on Wednesdays. The first homework assignment is due on Wednesday Feb 6th.

    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 (5%): 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 23) Lecture 1: Introduction to the Course and Enumeration (Chapter 1 of LPV, Secs 1.1-1.3)
  • (Jan 28 ) Lecture 2: Enumeration (Chapter 1 of LPV, Secs 1.4-1.8)
  • (Jan 30) Lecture 3: Induction and the Pigeon-hole Principle (Chapter 2 of LPV, Secs 2.1, 2.4)
  • (Feb 4) Lecture 4: Inclusion-Exclusion and Asymptotics (Chapter 2 of LPV, Secs 2.2-2.3, 2.5 )
  • (Feb 6) Lecture 5: The Binomial Theorem, more Identities in Pascal's Triangle, and choosing Multisets (Chapter 3 of LPV, Secs 3.1-3.6)
  • (Feb 11) Lecture 6: Generalized binomial coefficients and Fibonacci Numbers (Chapter 4 of LPV)
  • (Feb 13) Lecture 7: Fibonacci Numbers II (Chapter 4 of LPV)
  • (Feb 18) Lecture 8: Fibonacci Numbers III and a glimpse of generating functions (Chapter 4 of LPV and Generating Function Handout)
  • (Feb 20) Lecture 9: Number of Derangements (Handout courtesy of Dennis White)
  • (Feb 25) Exam 1: Covers class material through Feb 18th (Chapters 1-4 of LPV, not including Generating Functions nor Secs. 3.7-3.8)

  • (Feb 27) Lecture 10: Went over Exam 1 (see solutions below) and Introduction to Graph Theory (Sections 7.1-7.2 of LPV)
    Examples of Combinatorial Proofs I (Gary MacGillivray)
    Examples of Combinatorial Proofs II (Aruthur Benjamin and Jennifer Quinn)
  • (Mar 4) Lecture 11: Graph Theory II: Degree Sequences, Connectivity, and Subgraphs (Sections 7.1-7.2 of LPV)
  • (Mar 6) Lecture 12: Eulerian Walks and Hamiltonian Cycles and Introduction to Trees (Sections 7.3, 8.1-8.2 of LPV)
  • (Mar 11) Lecture 13: Tree Enumeration and Counting Labeled Trees of a Graph I (Sections 8.3-8.5 of LPV)
  • (Mar 13) Lecture 14: The Prufer code and Counting Labeled Trees of a Graph II (Sections 8.3-8.5 of LPV)
    and Counting closed walks in a graph and linear algebra review (Closed Walk Handout)
  • (Mar 18-22) Spring Break
  • (Mar 25) Lecture 15: More on Spanning Tree Enumeration and the Matrix Tree Theorem (Matrix Tree Theorem Handout)
  • (Mar 27) Lecture 16: Finding optimum trees and the Traveling Salesman Problem (Chapter 9 of LPV)
  • (Apr 1) Lecture 17: Perfect Matchings in Graphs and Bipartite Graphs (Sections 10.1-10.3 of LPV and Matching Handout) Handout courtesy of Dennis White
  • (Apr 3) Lecture 18: The Marriage Theorem, finding a perfect matching, and counting perfect matchings in graphs (Sections 10.3-10.4 of LPV)
  • (Apr 8) Exam 2: Covers class material from Feb 20th (Derangements) through April 1st (Perfect matchings and the Augmented Path Algorithm)

  • (Apr 10) Lecture 19: Counting intersections, regions, and triangulations (Sections 11.1-11.2 of LPV)
  • (Apr 15) Lecture 20: Catalan numbers (Catalan Number Handout) Handout courtesy of Dennis White
    Link to Richard Stanley's Catalan Number webpages here and here
  • (Apr 17) Lecture 21: Planar Graphs and Euler's Formula (Chapter 12 of LPV)
  • (Apr 22) Lecture 22: The Chromatic Polynomial (Chromatic Polynomial Handout) Handout courtesty of Dennis White
  • (Apr 24) Lecture 23: Chromatic Polynomials continued and Stanley's Theorem on Acyclic Orientations
  • (Apr 29) Lecture 24: A glimpse of my research: Cluster Algebras
    An Introduction to Cluster Algebras by Lauren Williams
    Slides from Fall 2012
    Diagram of the proof discussed in class
  • (May 1) Lecture 25: A Brief History of the Four Color Theorem (Chapter 13 of LPV)
  • (May 6) Lecture 26: Final Review
  • (May 8) Exam 3: Covers class material through May 1st


  • Homework assignments (tentative) and exams
    Assignment or Exam Due date Problems from Lovasz-Pelikan-Vesztergombi text,
    unless otherwise specified
    Homework 1 Wednesday Feb 6 Sec 1.8: # 12, 13, 14, 17, 22, 26, 29, 31, 33, 34
    Sec 2.5: # 1, 3, 4 (b), 5, 7, 8
    Solutions: here
    Homework 2 Wednesday Feb 20 Sec 3.4: # 1 (Make sure to explain your answer.)
    Sec. 3.8: # 6, 8, 9, 10, 12, 13
    Sec. 4.3: # 2, 5, 6, 9 (b)-(c), 13, 14 (a)-(c), 15
    One supplementary problem: here
    Solutions: here
    Exam 1 Monday Feb 25 Solutions: here
    Homework 3 Wednesday Mar 13 Sec 7.3 # 4, 5, 8, 10
    Sec 8.5 # 3, 4, 6, 7
    Five additional problems (for credit!) here
    Solutions: here
    Homework 4 Wednesday Apr 3 Sec 8.5 # 5, 8, 9 11, 12
    Sec 9.2 # 3
    Three additional problems here.
    Solutions: here
    Exam 2 Monday Apr 8 Solutions: here
    Homework 5 Wednesday Apr 24 Sec 11.3 # 2, 3
    From Catalan Numbers Notes and Worksheet: # 2, 4, 5, 6, 10
    Sec 12.3 # 2, 4, 5, 6

    Errata:
    For Problem 12.3.5, the Petersen graph is Figure 7.13 on page 139 of LPV.
    For Problem 12.3.6, the phrase "exactly 12 pentagonal faces" should read "at least 12 pentagonal faces".
    Solutions: here
    Homework 6 Monday May 6 Seven problems on the following handout
    Solutions: here
    Exam 3 Wednesday May 8 Solutions: here