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.
Discrete Math Courses [Show]Discrete Math Courses [Hide]
MAT 375: Introduction to Graph Theory
This course, taught by Professor 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 it after the first lecture.
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. It is important to note that the course is cross-listed with COS 342, and is therefore also a computer science departmental.
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 grade is based on eleven problem sets through the semester, and on a ten-problem take-home final exam. The problem sets are instructive, and often end up teaching new material outside of class. Professor Seymour always goes over all the homework problems every week after they are handed in. Collaboration is allowed, and heavily encouraged.
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 and a somewhat substantial time commitment. Collaboration is encouraged and asking the TAs for help is not at all uncommon.
MAT 377: Combinatorial Mathematics
This course is taught by Professor van Zwam, 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.
MAT 378: Game Theory
Professor van Zwam’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.
MAT 584: Incidence Theorems and their Applications
This is Professor Dvir’s graduate course on Incidence Theorems and their applications. The titular theorems are a way of formally describing how discrete shapes such as lines, points and various other geometric objects intersect each other. These theorems have recently risen in importance because of their tremendous applications. The course serves as a rigorous introduction to this vast and wonderful theory, proving some of its major results. The course delves into problems such as Szemeredi-Trotter problems (“How many incidences can a set of lines have with a set of points?”), Kakeya problems (“What are the properties of sets in Euclidean space containing line segments in each direction?”), as well as Sylvester-Gallai problems (“Is it possible to have a non-collinear set of points such that a line through any two of them must go through a third?”). The topics covered in this graduate course have far-reaching consequences in some of the most important areas of modern research, such as additive combinatorics, coding theory and computational complexity.
Professor Dvir follows his own excellent notes, which are available on his website. The same page also details some additional readings for the interested reader. The course is aimed primarily at graduate students, although undergraduates with sufficient background in mathematics and computer science are encouraged to try it as well. As with all mathematics graduate courses, the undergraduates have to solve a few problems in order to pass the course, though typically this is more a formality than a stringent requirement.
The course is rewarding but challenging, and any undergraduate student planning on taking it is advised to read up as much background material as possible in order to follow the lectures easily. It also helps to be interested in computer science, as then the motivation behind much of the material becomes evident.
MAT 595: Topics in Discrete Mathematics
This graduate topics course is usually offered by Professor Seymour (the matroid theory course has also been offered by Professor van Zwam). 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.
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. Essentially, the course is divided into two halves. 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), and then 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. Furthermore, a student who knows complex analysis is at a great advantage towards the beginning of the second half of the course. 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 is also known to be very generous with his final grades.
Although the “discrete” part of this course is confined to the first half, it is a course worth taking. Professor Sedgewick loves teaching the class, and takes great care to ensure that the content is well understood by everyone. Furthermore, it is useful in simplifying a number of problems that come up a lot in “real-life computer science,” and solving them with the aid of the beautiful but counter-intuitive approaches arising from mathematics.