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

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

Examples of Combinatorial Proofs I (Gary MacGillivray)

Examples of Combinatorial Proofs II (Aruthur Benjamin and Jennifer Quinn)

and Counting closed walks in a graph and linear algebra review (Closed Walk Handout)

Link to Richard Stanley's Catalan Number webpages here and here

An Introduction to Cluster Algebras by Lauren Williams

Slides from Fall 2012

Diagram of the proof discussed in class

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 |