Applied Combinatorics

At Georgia Tech, MATH 3012: Applied Combinatorics, is a junior-level course targeted primarily at students pursuing the B.S. in Computer Science. The purpose of the course is to give students a broad exposure to combinatorial mathematics, using applications to emphasize fundamental concepts and techniques. Applied Combinatorics is also required of students seeking the B.S. in Mathematics, and it is one of two discrete mathematics courses that computer engineering students may select to fulfill a breadth requirement. The course will also often contain a selection of other engineering and science majors who are interested in learning more mathematics. As a consequence, in a typical semester, some 250 Georgia Tech students are enrolled in Applied Combinatorics. Students enrolled in Applied Combinatorics at Georgia Tech have already completed the three semester calculus sequence—with many students bypassing one or more of the these courses on the basis of advanced placement scores. Also, the students will know some linear algebra and can at least have a reasonable discussion about vector spaces, bases and dimension.

Our approach to the course is to show students the beauty of combinatorics and how combinatorial problems naturally arise in many settings, particularly in computer science. While proofs are periodically presented in class, the course is not intended to teach students how to write proofs; there are other required courses in our curriculum that meet this need. Students may occasionally be asked to prove small facts, but these arguments are closer to the kind we expect from students in second or third semester calculus as contrasted with proofs we expect from a mathematics major in an upper-division course. Regardless, we cut very few corners, and our text can readily be used by instructors who elect to be even more rigorous in their approach.

This book arose from our feeling that a text that met our approach to Applied Combinatorics was not available. Because of the diverse set of instructors assigned to the course, the standard text was one that covered every topic imaginable (and then some), but provided little depth. We’ve taken a different approach, attacking the central subjects of the course description to provide exposure, but taking the time to go into greater depth in select areas to give the students a better feel for how combinatorics works. We have also included some results and topics that are not found in other texts at this level but help reveal the nature of combinatorics to students. We want students to understand that combinatorics is a subject that you must feel “in the gut”, and we hope that our presentation achieves this goal. The emphasis throughout remains on applications, including algorithms. We do not get deeply into the details of what it means for an algorithm to be “efficient”, but we do include an informal discussion of the basic principles of complexity, intended to prepare students in computer science, engineering and applied mathematics for subsequent coursework.

The materials included in this book have evolved over time. Early versions of a few chapters date from 2004, but the pace quickened in 2006 when the authors team taught a large section of Applied Combinatorics. In the last five years, existing chapters have been updated and expanded, while new chapters have been added. As matters now stand, our book includes more material than we can cover in a single semester. We feel that the topics of Chapters 1–9 plus Chapters 12, 13 and 14 are the core of a one semester course in Applied Combinatorics. Additional topics can then be selected from the remaining chapters based on the interests of the instructor and students.