Combinatorics

MAT 145 - Summer Session 2011

Department of Mathematics
University of California, Davis

Instructor: Matthew Stamps
Lectures: MWF 2:10-3:50, Physics 140
Office: Mathematical Sciences 2125
Office Hours: M 4:00-5:00 & W 10:00-11:00
Email: m t s t a m p s @ m a t h . u c d a v i s . e d u

Welcome to Math 145 - an introduction to the fascinating subject of combinatorics! This course will cover material from both abstract and practical perspectives, rigorously developing the theory while consistently motivating it through applications. Consequently, the course will appeal to both pure and applied mathematics students. Students with interests in computer science are also encouraged to enroll.

While the only formal prerequisite for this class is MATH 21B, students should be prepared to work on, construct, and carefully write logical arguments and proofs. The focus will not be on memorizing a set of standard formulas or techniques, which may be different from previous math courses. Instead, the aim of the course is to develop problem-solving skills that can be applied in many mathematical settings.

Course Overview

Combinatorics is the study of finite or countable structures. Many questions center around understanding the relationship between a finite set of objects, and counting such objects. Combinatorial problems arise in many areas of pure mathematics, notably in algebra, geometry, topology, and probability theory, and have many applications in optimization, computer science, decision theory, and physics.

Textbook and Syllabus

The course textbook is "Discrete Mathematics: Elementary and Beyond" by László Lovász, József Pelikán, and Katalin L. Vesztergombi. We will follow the book loosely, at best, so it is imperative that you attend lectures regularly. The major topics include:

  • an introduction to combinatorial proof (Fibonacci and binomial coefficient identities; generating functions)
  • enumeration techniques (inclusion-exclusion and pigeonhole principles)
  • graph theory (paths and cycles; trees, matchings, and optimization; colorings; planarity)
  • advanced topics (discrete geometry; algebraic and topological combinatorics)
For supplemental reading, see "Proofs that Really Count" by Arthur T. Benjamin and Jennifer J. Quinn; "Concrete Mathematics" by Ronald L. Graham, Donald E. Knuth, and Oren Patashnik; "Pearls in Graph Theory" by Nora Hartsfield and Gerhard Ringel; and "A Walk Through Combinatorics" by Miklós Bóna.

The UC Davis Mathematics Department has an official syllabus for the course posted here.

Evaluation & Assessment

There will be four homework sets, a midterm, and a final exam. The development of problem-solving skills is a significant part of this course, so it is very important that students take the problem sets seriously. As such, final scores will be weighted as follows:
  • Homework 50%
  • Midterm 25%
  • Final Exam 25%
Grades will be assigned on a soft curve, meaning that I will not predetermine either what scores correspond to what grades, or what percentage of students get what grades. If the entire class does well enough, I will give all A's and B's.

Homework

Problem sets will be posted on the course webpage (below) and due every two weeks. Students are encouraged to collaborate on the homework, but all write-ups should be done individually. In general, there will be no make-ups or extensions. Students are expected to write their solutions legibly and turn them in at the beginning of lecture on each due date. Instructor solutions will be posted promptly after each assignment.

Exams

The Midterm will be given during lecture Friday, July 15. It will cover material from the first half of the course.

Midterm Solutions

The Final Exam will be given during lecture Friday, August 12. It will be comprehensive with focus mainly on material from the second half of the course.

Practice Final Solution Set #1 Solution Set #2 (Ignore Problems 5 and 9(b))

There will be no make-up exams. Students should contact the instructor immediately if they have an unavoidable scheduling conflict with either of the exam dates.

Students with Disabilities

Any student with a documented disability (e.g. physical, learning, psychiatric, vision, hearing, etc.) who needs to arrange reasonable accommodations must contact the Student Disability Center (SDC). Faculty are authorized to provide only the accommodations requested by the SDC. If you have any questions, please contact the SDC at (530) 752-3184 or sdc@ucdavis.edu.