Discrete mathematics, broadly speaking, is the “study of discrete objects.” As opposed to objects that vary smoothly, such as the real numbers, discrete mathematics has been described as the mathematics of countable sets. Because of the absence of an all-encompassing definition, the best way to understand what discrete mathematics entails is to enumerate some of the topics it covers: graph theory, combinatorics, set theory, logic, discrete probability theory, number theory, certain topics in algebra (numerical semigroups and monoids, for instance), discrete geometry, and several topics in game theory.
Of these topics, Princeton offers separate courses on graph theory, combinatorics, logic, discrete geometry, and game theory. Set theory, number theory, probability, and the “discrete” topics in algebra come up in their own right in various other courses, where they can be studied in more depth.
Finally, it should be stated that discrete mathematics is very closely associated with computer science. As a result, many of the topics can be studied as integral parts of either of the two disciplines. In fact, there are a couple of courses offered by Princeton’s COS department which are really discrete mathematics courses in disguise. Students majoring in either of the two also often end up taking courses from the other, and as a result there is constant exchange and collaboration between the two departments.
In order to graduate with a degree in mathematics, it is required to take one course in discrete mathematics, geometry or topology.
Introductory courses
MAT 375: Introduction to Graph Theory (also COS 342)
This course, taught alternately by Professors Chudnovsky and Seymour, serves as the “standard” Princeton introduction to discrete mathematics. The course covers the fundamental theorems and algorithms used in graph theory. Since there is not enough time to build the deeper results in graph theory, the course is based on breadth rather than depth, and therefore goes through a host of topics. These include connectivity, matching, graph coloring, planarity, the celebrated Four Color Theorem, extremal problems, network flows, and many related algorithms which are often of significance to computer science. Professor Seymour is one of the greatest graph theorists that the world has ever seen, and the course is designed and taught by him; it is, consequently, a unique experience that not many other universities can provide. He uses his own course notes, which have evolved through the last couple of decades, and are notorious for their terse expositions (“Proof: Trivial.”) as well as the large amount of material condensed into them. Professor Seymour also recommends Douglas West’s classic graph theory textbook, although he rarely consults. The course is meant for a wide range of students. Since it assumes no background except with the basics of mathematical reasoning, it is one of the largest departmental courses offered by Princeton Mathematics. Students taking the course range from the mathematics majors who intend to specialize in graph theory to students who need a “theoretical” requirement for their Princeton academic career: a huge contingent of the class is comprised of computer science majors, who are interested in the connections between graph theory and computer science. The class starts slowly, but picks up very fast as it goes into more and more material. Although it is almost universally agreed as a “fun” class, doing well can be challenging, since there is a scramble for the higher grades – the class is notorious for yielding medians of 9.8 out of 10 in its weekly problem sets. The problem sets are instructive, and often end up teaching new material outside of class. Professors Chudnovsky and Seymour always go over all the homework problems every week after they are handed in. All in all, the course is well-organized, brilliantly taught, and extremely fun and accessible to students of all levels. However, doing well in the course requires hard work. Collaboration is encouraged and asking the TAs for help is not at all uncommon.
Offered in the Spring.
What to take after? Advanced Graph Theory.
MAT 377: Combinatorial Mathematics
This course was most recently taught by Professor Alon, and functions as the standard undergraduate introduction to non-graph-theoretic combinatorics. Combinatorics, the theory of “counting,” is an indispensable tool and integral component of many areas of mathematics; but more importantly, it has recently, in light of modern research, grown into a fundamental mathematical discipline in its own right. This modern theory relies on deep, well-developed tools, some of which the course gets into. In essence, the course covers over a dozen virtually independent topics illustrating some of the most powerful theorems of modern combinatorics, such as Ramsey Theory, Turan-type theorems, extremal graph theory, probabilistic combinatorics, algebraic combinatorics, and spectral techniques in graph theory.
This course is meant primarily for mathematics majors looking for an introduction to the theory of combinatorics. The class, therefore, is typically much smaller than its “predecessor,” MAT 375. Professor van Zwam uses his own notes and supplements them with some of the classic expository texts in combinatorics, such as Peter Cameron’s notes or Richard Stanley’s book. Students are highly encouraged to take notes during lectures, since they are usually not put up online. Another useful resource is Jacob Fox’s notes from the same course, which was taught by him in earlier years.
There are about six problem sets spread evenly through the semester. Each contains about five or six problems, which get steadily more and more challenging. Collaboration, therefore, is an important part of the course. Students have been known to stay up for several nights working on a couple of seemingly impossible problems towards the end. However, this is an effort to introduce students to basic combinatorics research, and is an important part of the course; solutions are discussed in depth after the problems are handed in.
There is a take-home final with six problems, which collectively involve techniques learned throughout the semester. As a recapitulation of these broad techniques, the final is a brilliant but completely reasonable test of what the students are expected to have taken out of the course. Therefore, it is easy to do well on the course as long as a student has attended the lectures and learned the general principles.
An important part of the course is the last two or three weeks, when it departs from the traditional topics taught in similar courses in other universities, and delves into some of the modern research in combinatorics. In particular, the lectures on spectral graph theory and the basic introduction to matroid theory are extremely rewarding, since Professor van Zwam himself is a matroid theorist. There is usually less homework assigned from this part, but the material is wonderfully presented by Professor van Zwam; these last couple of lectures also serve as sufficient background to the graduate course on matroid theory, MAT 595.
Offered in the Fall.
What to take after? Extremal Combinatorics.
MAT 378: Theory of Games
Professor Fickenscher’s course on game theory the only class that the mathematics department offers on the subject (there are other classes on game theory offered by other departments). Game theory is the formal mathematical study of strategic decision-making; consequently it deals with a number of scenarios where one person’s success depends on others’ choices, and therefore choosing the “right” course of action is a complex calculation. Game theory is not entirely a subset of discrete mathematics, since a lot of the more modern results in it are much more continuous in nature; however, given the large discrete component of the discipline, it deserves mention in this category.
Offered in the Spring.
Advanced courses
MAT 477: Advanced Graph Theory
MAT 478: Topics in Combinatorics: Extremal Combinatorics (also MAT 577)
This is a new course (as of Spring 2019) taught by Professor Alon, where he presents relatively new results (new enough that he was the first to prove many of them!) in the information theory of graphs, including the relationships between the independence, clique, fractional clique, Lovasz and Shannon numbers of graphs and graph powers. Professor Alon is an extremely organized and informational lecturer, and the course is extremely valuable in its insight to this very approachable but difficult subfield. Prior course experience in combinatorics is of use but is by no means required.
Offered in the Spring.
What to take before? Graph Theory, Combinatorics.
MAT 57x: Topics in Discrete Mathematics
This graduate topics course is usually offered by Professors Chudnovsky or Seymour. The course changes from semester to semester, but is usually one of the three following topics.
Matroid Theory: This class is offered by either Professor Seymour or Professor van Zwam, and serves as a rigorous introduction to matroids, which are discrete structures similar to graphs that exhibit properties of rank and linear independence. This theory is young and exciting, and the course covers most of its seminal results in addition to going into current research topics. The instructor’s notes are usually used in conjunction with Oxley’s classic textbook.
Structural Graph Theory – Induced Subgraphs: This course is an introduction to the theory of induced subgraphs, building up gradually to the celebrated 2002 proof of the Strong Perfect Graph Theorem (a graph is perfect if and only if it is a Berge graph). Like its counterpart, the Graph Minors course, this course is about structural graph theory, which is traditionally one of the “hardest” branches of combinatorics, and hence students are expected to be comfortable with long proofs and extremely intricate arguments.
Structural Graph Theory – Graph Minors: This course is a fast but intensive run through some of the results of the famous Graph Minors Project of Seymour and Robertson. The course builds up a lot of the theory behind containment relations such as minors, subgraphs, immersions and topological containment, and then goes into structure theorems and many forbidden-minor characterizations. Using pathwidth, treewidth and branchwidth, the course then develops most of the necessary tools for attacking Seymour and Robertson’s celebrated Graph Minor Theorem (graphs are well-quasi-ordered under minors), and sketches the proof.
The discrete mathematics graduate course is rewarding in the extreme, since it is taught by the best in the world. Any student planning on taking it, however, should be prepared to put in a lot of time for the problem sets. Some of the homework problems, be warned, have been unsolved and are (still) open.
Another point that should be kept in mind is that knowing the material from MAT 375 is really a pre-requisite to taking this course. The first lecture is sometimes a refresher, but unless a student already knows some standard techniques in graph theory beforehand, even the refresher does not help. This should be kept in mind because of the frenetic nature of the course; it delves into quite advanced material from the second lecture onwards.
What to take before? Graph Theory, Advanced Graph Theory.
CS courses that are basically discrete math courses
There are many COS courses that are mathematical in the presentation of content, problem sets, and even listing in the course catalogue. Here, we have a selection of
COS 423: Theory of Algorithms
Offered in the Spring.
COS 433: Cryptography (also MAT 473)
Offered in the Spring.
COS 451: Computational Geometry
Offered in the Fall.
COS 487: Theory of Computation (also MAT 407)
Offered in the Fall.
COS 488: Analytic Combinatorics
This course of Professor Sedgewick’s serves as an introduction to one of the most powerful recent techniques in algorithm analysis. The discipline of analytic combinatorics represents many decades of collaboration between Professor Sedgewick and Phillipe Flajolet. In the first half, the course covers techniques from classical combinatorics to tackle “hard” approximation problems that come up in computer science (particularly in the analysis of certain recursion-based algorithms). In the second half, it goes into deeper mathematics in order to deal with more general classes of problems by using techniques from complex analysis. This course is very unique, in that it really is a mathematics class; there is next to no coding, and not much mention of computer science. However, unlike most mathematics classes, it switches gears in the middle, and moves from discrete to continuous mathematics, but with the same end in sight. Not much background is required for the class, though some familiarity with algorithm analysis helps distinctly. Knowledge of complex analysis is a great advantage in the beginning of the second half. Professor Sedgewick encourages collaboration and is one of the most organized lecturers at Princeton, so the course ends up being accessible to anyone interested in taking it; he loves teaching the class, and takes great care to ensure that the content is well understood by everyone.
Offered in the Spring.
What to take before?
COS 522: Computational Complexity (also MAT 578)
Offered in the Spring.
Contacts
Rik Sengupta ’12 (rsengupt[at]mit[dot]edu)