Applied Combinatorics

SF2730 Selected Topics in Mathematics V
Sessions II & III of 2014-2015

Department of Mathematics
Royal Institute of Technology, Stockholm

Instructor: Matthew Stamps
Email:

Lectures: Tuesdays 15:15-17:00, Room 3721 (The first class meeting is November 4.)
Office Hours: Mondays 17:00-18:00 & Fridays 10:00-11:00, Room 3629

Welcome to SF2730 - An introduction to the fascinating subject of applied combinatorics! This course will cover material from both abstract and practical perspectives, rigorously developing the theory while consistently motivating it through applications. Consequently, it should appeal to students from across the mathematics, computer science, and engineering disciplines.

While there are no specific prerequisites for this course, we shall assume familiarity with basic enumeration and linear algebra. Additionally, 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 other math courses. Instead the aim of this class is to develop problem-solving skills that can be applied thorughout a variety of mathematical and computational 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 enumerating or 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 "Concrete Mathematics" by Ronald L. Graham, Donald E. Knuth, and Oren Patashnik. 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)
  • solving recurrences (ordinary and exponential generating functions, Cayley's theorem)
  • special numbers (Catalan numbers, Stirling numbers, Bell numbers, Harmonic numbers, Bernoulli numbers, etc)
  • enumeration with symmetry (group actions, Burnside's lemma, orbit-stabilizer theorem)
  • spectral graph theory (adjacency matrices, the matrix-tree theorem, minimally weighted spanning trees, Cayley's theorem revisited)
  • geometric combinatorics (applications of Sperner's lemma to fair division)
  • coding theory (error-correcting codes, Shannon's theorem)
For supplemental reading, see "Combinatorics: Topics, Techniques, Algorithms" by Peter J. Cameron; "Proofs that Really Count" by Arthur T. Benjamin and Jennifer J. Quinn; and "A Walk Through Combinatorics" by Miklós Bóna.

An official syllabus for the course will be posted here shortly.

Evaluation & Assessment

There will be weekly homework sets, a project, 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 grades will be weighted as follows:
  • Homework 60%
  • Project 10%
  • Final Exam 30%

Homework

Problem sets will be posted (below) on the course webpage and due roughly every week. Students are encouraged to collaborate on the homework, but all write-ups must be done individually. In general, there will be no make-ups or extensions.

Project

The project will consist of writing a short paper on a prescribed topic related to applied combinatorics. A list of preapproved topics will be posted half way through the course.

Exam

The Final Exam will be given TBA. It will be comprehensive, i.e., covering material from throughout the entire course.

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