Dis­crete math­e­mat­ics, broadly speak­ing, is the “study of dis­crete objects.” As opposed to objects that vary smoothly, such as the real num­bers, dis­crete math­e­mat­ics has been described as the math­e­mat­ics of count­able sets. Because of the absence of an all-encompassing def­i­n­i­tion, the best way to under­stand what dis­crete math­e­mat­ics entails is to enu­mer­ate some of the top­ics it cov­ers: graph the­ory, com­bi­na­torics, set the­ory, logic, dis­crete prob­a­bil­ity the­ory, num­ber the­ory, cer­tain top­ics in alge­bra (numer­i­cal semi­groups and monoids, for instance), dis­crete geom­e­try, and sev­eral top­ics in game theory.

Of these top­ics, Prince­ton offers sep­a­rate courses on graph the­ory, com­bi­na­torics, logic, dis­crete geom­e­try, and game the­ory. Set the­ory, num­ber the­ory, prob­a­bil­ity, and the “dis­crete” top­ics in alge­bra come up in their own right in var­i­ous other courses, where they can be stud­ied in more depth.

Finally, it should be stated that dis­crete math­e­mat­ics is very closely asso­ci­ated with com­puter sci­ence. As a result, many of the top­ics can be stud­ied as inte­gral parts of either of the two dis­ci­plines. In fact, there are a cou­ple of courses offered by Princeton’s COS depart­ment which are really dis­crete math­e­mat­ics courses in dis­guise. Stu­dents major­ing in either of the two also often end up tak­ing courses from the other, and as a result there is con­stant exchange and col­lab­o­ra­tion between the two departments.

Dis­crete Math Courses [Show]Dis­crete Math Courses [Hide]
MAT 375: Intro­duc­tion to Graph The­ory
This course, taught by Pro­fes­sor Sey­mour, serves as the “stan­dard” Prince­ton intro­duc­tion to dis­crete math­e­mat­ics. The course cov­ers the fun­da­men­tal the­o­rems and algo­rithms used in graph the­ory. Since there is not enough time to build the deeper results in graph the­ory, the course is based on breadth rather than depth, and there­fore goes through a host of top­ics. These include con­nec­tiv­ity, match­ing, graph col­or­ing, pla­narity, the cel­e­brated Four Color The­o­rem, extremal prob­lems, net­work flows, and many related algo­rithms which are often of sig­nif­i­cance to com­puter sci­ence.
Pro­fes­sor Sey­mour is one of the great­est graph the­o­rists that the world has ever seen, and the course is designed and taught by him; it is, con­se­quently, a unique expe­ri­ence that not many other uni­ver­si­ties can pro­vide. He uses his own course notes, which have evolved through the last cou­ple of decades, and are noto­ri­ous for their terse expo­si­tions (“Proof: Triv­ial.”) as well as the large amount of mate­r­ial con­densed into them. Pro­fes­sor Sey­mour also rec­om­mends Dou­glas West’s clas­sic graph the­ory text­book, although he rarely con­sults it after the first lec­ture.
The course is meant for a wide range of stu­dents. Since it assumes no back­ground except with the basics of math­e­mat­i­cal rea­son­ing, it is one of the largest depart­men­tal courses offered by Prince­ton Math­e­mat­ics. Stu­dents tak­ing the course range from the math­e­mat­ics majors who intend to spe­cial­ize in graph the­ory to stu­dents who need a “the­o­ret­i­cal” require­ment for their Prince­ton aca­d­e­mic career. A huge con­tin­gent of the class is com­prised of com­puter sci­ence majors, who are inter­ested in the con­nec­tions between graph the­ory and com­puter sci­ence. It is impor­tant to note that the course is cross-listed with COS 342, and is there­fore also a com­puter sci­ence depart­men­tal.
The class starts slowly, but picks up very fast as it goes into more and more mate­r­ial. Although it is almost uni­ver­sally agreed as a “fun” class, doing well can be chal­leng­ing, since there is a scram­ble for the higher grades – the class is noto­ri­ous for yield­ing medi­ans of 9.8 out of 10 in its weekly prob­lem sets.
The grade is based on eleven prob­lem sets through the semes­ter, and on a ten-problem take-home final exam. The prob­lem sets are instruc­tive, and often end up teach­ing new mate­r­ial out­side of class. Pro­fes­sor Sey­mour always goes over all the home­work prob­lems every week after they are handed in. Col­lab­o­ra­tion is allowed, and heav­ily encour­aged.
All in all, the course is well-organized, bril­liantly taught, and extremely fun and acces­si­ble to stu­dents of all lev­els. How­ever, doing well in the course requires hard work and a some­what sub­stan­tial time com­mit­ment. Col­lab­o­ra­tion is encour­aged and ask­ing the TAs for help is not at all uncom­mon.
MAT 377: Com­bi­na­to­r­ial Math­e­mat­ics
This course is taught by Pro­fes­sor van Zwam, and func­tions as the stan­dard under­grad­u­ate intro­duc­tion to non-graph-theoretic com­bi­na­torics. Com­bi­na­torics, the the­ory of “count­ing,” is an indis­pens­able tool and inte­gral com­po­nent of many areas of math­e­mat­ics; but more impor­tantly, it has recently, in light of mod­ern research, grown into a fun­da­men­tal math­e­mat­i­cal dis­ci­pline in its own right. This mod­ern the­ory relies on deep, well-developed tools, some of which the course gets into. In essence, the course cov­ers over a dozen vir­tu­ally inde­pen­dent top­ics illus­trat­ing some of the most pow­er­ful the­o­rems of mod­ern com­bi­na­torics, such as Ram­sey The­ory, Turan-type the­o­rems, extremal graph the­ory, prob­a­bilis­tic com­bi­na­torics, alge­braic com­bi­na­torics, and spec­tral tech­niques in graph the­ory.
This course is meant pri­mar­ily for math­e­mat­ics majors look­ing for an intro­duc­tion to the the­ory of com­bi­na­torics. The class, there­fore, is typ­i­cally much smaller than its “pre­de­ces­sor,” MAT 375. Pro­fes­sor van Zwam uses his own notes and sup­ple­ments them with some of the clas­sic expos­i­tory texts in com­bi­na­torics, such as Peter Cameron’s notes or Richard Stanley’s book. Stu­dents are highly encour­aged to take notes dur­ing lec­tures, since they are usu­ally not put up online. Another use­ful resource is Jacob Fox’s notes from the same course, which was taught by him in ear­lier years.
There are about six prob­lem sets spread evenly through the semes­ter. Each con­tains about five or six prob­lems, which get steadily more and more chal­leng­ing. Col­lab­o­ra­tion, there­fore, is an impor­tant part of the course. Stu­dents have been known to stay up for sev­eral nights work­ing on a cou­ple of seem­ingly impos­si­ble prob­lems towards the end. How­ever, this is an effort to intro­duce stu­dents to basic com­bi­na­torics research, and is an impor­tant part of the course; solu­tions are dis­cussed in depth after the prob­lems are handed in.
There is a take-home final with six prob­lems, which col­lec­tively involve tech­niques learned through­out the semes­ter. As a reca­pit­u­la­tion of these broad tech­niques, the final is a bril­liant but com­pletely rea­son­able test of what the stu­dents are expected to have taken out of the course. There­fore, it is easy to do well on the course as long as a stu­dent has attended the lec­tures and learned the gen­eral prin­ci­ples.
An impor­tant part of the course is the last two or three weeks, when it departs from the tra­di­tional top­ics taught in sim­i­lar courses in other uni­ver­si­ties, and delves into some of the mod­ern research in com­bi­na­torics. In par­tic­u­lar, the lec­tures on spec­tral graph the­ory and the basic intro­duc­tion to matroid the­ory are extremely reward­ing, since Pro­fes­sor van Zwam him­self is a matroid the­o­rist. There is usu­ally less home­work assigned from this part, but the mate­r­ial is won­der­fully pre­sented by Pro­fes­sor van Zwam; these last cou­ple of lec­tures also serve as suf­fi­cient back­ground to the grad­u­ate course on matroid the­ory, MAT 595.
MAT 378: Game The­ory
Pro­fes­sor van Zwam’s course on game the­ory the only class that the math­e­mat­ics depart­ment offers on the sub­ject (there are other classes on game the­ory offered by other depart­ments). Game the­ory is the for­mal math­e­mat­i­cal study of strate­gic decision-making; con­se­quently it deals with a num­ber of sce­nar­ios where one person’s suc­cess depends on oth­ers’ choices, and there­fore choos­ing the “right” course of action is a com­plex cal­cu­la­tion. Game the­ory is not entirely a sub­set of dis­crete math­e­mat­ics, since a lot of the more mod­ern results in it are much more con­tin­u­ous in nature; how­ever, given the large dis­crete com­po­nent of the dis­ci­pline, it deserves men­tion in this cat­e­gory.
MAT 584: Inci­dence The­o­rems and their Appli­ca­tions
This is Pro­fes­sor Dvir’s grad­u­ate course on Inci­dence The­o­rems and their appli­ca­tions. The tit­u­lar the­o­rems are a way of for­mally describ­ing how dis­crete shapes such as lines, points and var­i­ous other geo­met­ric objects inter­sect each other. These the­o­rems have recently risen in impor­tance because of their tremen­dous appli­ca­tions. The course serves as a rig­or­ous intro­duc­tion to this vast and won­der­ful the­ory, prov­ing some of its major results. The course delves into prob­lems such as Szemeredi-Trotter prob­lems (“How many inci­dences can a set of lines have with a set of points?”), Kakeya prob­lems (“What are the prop­er­ties of sets in Euclid­ean space con­tain­ing line seg­ments in each direc­tion?”), as well as Sylvester-Gallai prob­lems (“Is it pos­si­ble to have a non-collinear set of points such that a line through any two of them must go through a third?”). The top­ics cov­ered in this grad­u­ate course have far-reaching con­se­quences in some of the most impor­tant areas of mod­ern research, such as addi­tive com­bi­na­torics, cod­ing the­ory and com­pu­ta­tional com­plex­ity.
Pro­fes­sor Dvir fol­lows his own excel­lent notes, which are avail­able on his web­site. The same page also details some addi­tional read­ings for the inter­ested reader. The course is aimed pri­mar­ily at grad­u­ate stu­dents, although under­grad­u­ates with suf­fi­cient back­ground in math­e­mat­ics and com­puter sci­ence are encour­aged to try it as well. As with all math­e­mat­ics grad­u­ate courses, the under­grad­u­ates have to solve a few prob­lems in order to pass the course, though typ­i­cally this is more a for­mal­ity than a strin­gent require­ment.
The course is reward­ing but chal­leng­ing, and any under­grad­u­ate stu­dent plan­ning on tak­ing it is advised to read up as much back­ground mate­r­ial as pos­si­ble in order to fol­low the lec­tures eas­ily. It also helps to be inter­ested in com­puter sci­ence, as then the moti­va­tion behind much of the mate­r­ial becomes evi­dent.
MAT 595: Top­ics in Dis­crete Math­e­mat­ics
This grad­u­ate top­ics course is usu­ally offered by Pro­fes­sor Sey­mour (the matroid the­ory course has also been offered by Pro­fes­sor van Zwam). The course changes from semes­ter to semes­ter, but is usu­ally one of the three fol­low­ing top­ics.
Matroid The­ory: This class is offered by either Pro­fes­sor Sey­mour or Pro­fes­sor van Zwam, and serves as a rig­or­ous intro­duc­tion to matroids, which are dis­crete struc­tures sim­i­lar to graphs that exhibit prop­er­ties of rank and lin­ear inde­pen­dence. This the­ory is young and excit­ing, and the course cov­ers most of its sem­i­nal results in addi­tion to going into cur­rent research top­ics. The instructor’s notes are usu­ally used in con­junc­tion with Oxley’s clas­sic text­book.
Struc­tural Graph The­ory – Induced Sub­graphs: This course is an intro­duc­tion to the the­ory of induced sub­graphs, build­ing up grad­u­ally to the cel­e­brated 2002 proof of the Strong Per­fect Graph The­o­rem (a graph is per­fect if and only if it is a Berge graph). Like its coun­ter­part, the Graph Minors course, this course is about struc­tural graph the­ory, which is tra­di­tion­ally one of the “hard­est” branches of com­bi­na­torics, and hence stu­dents are expected to be com­fort­able with long proofs and extremely intri­cate argu­ments.
Struc­tural Graph The­ory – Graph Minors: This course is a fast but inten­sive run through some of the results of the famous Graph Minors Project of Sey­mour and Robert­son. The course builds up a lot of the the­ory behind con­tain­ment rela­tions such as minors, sub­graphs, immer­sions and topo­log­i­cal con­tain­ment, and then goes into struc­ture the­o­rems and many forbidden-minor char­ac­ter­i­za­tions. Using path­width, treewidth and branch­width, the course then devel­ops most of the nec­es­sary tools for attack­ing Sey­mour and Robertson’s cel­e­brated Graph Minor The­o­rem (graphs are well-quasi-ordered under minors), and sketches the proof.
The dis­crete math­e­mat­ics grad­u­ate course is reward­ing in the extreme, since it is taught by the best in the world. Any stu­dent plan­ning on tak­ing it, how­ever, should be pre­pared to put in a lot of time for the prob­lem sets. Some of the home­work prob­lems, be warned, have been unsolved and are (still) open.
Another point that should be kept in mind is that know­ing the mate­r­ial from MAT 375 is really a pre-requisite to tak­ing this course. The first lec­ture is some­times a refresher, but unless a stu­dent already knows some stan­dard tech­niques in graph the­ory before­hand, even the refresher does not help. This should be kept in mind because of the fre­netic nature of the course; it delves into quite advanced mate­r­ial from the sec­ond lec­ture onwards.
COS 488: Ana­lytic Com­bi­na­torics
This course of Pro­fes­sor Sedgewick’s serves as an intro­duc­tion to one of the most pow­er­ful recent tech­niques in algo­rithm analy­sis. The dis­ci­pline of ana­lytic com­bi­na­torics rep­re­sents many decades of col­lab­o­ra­tion between Pro­fes­sor Sedgewick and Phillipe Fla­jo­let. Essen­tially, the course is divided into two halves. In the first half, the course cov­ers tech­niques from clas­si­cal com­bi­na­torics to tackle “hard” approx­i­ma­tion prob­lems that come up in com­puter sci­ence (par­tic­u­larly in the analy­sis of cer­tain recursion-based algo­rithms), and then in the sec­ond half, it goes into deeper math­e­mat­ics in order to deal with more gen­eral classes of prob­lems by using tech­niques from com­plex analy­sis.
This course is very unique, in that it really is a math­e­mat­ics class; there is next to no cod­ing, and not much men­tion of com­puter sci­ence. How­ever, unlike most math­e­mat­ics classes, it switches gears in the mid­dle, and moves from dis­crete to con­tin­u­ous math­e­mat­ics, but with the same end in sight. Not much back­ground is required for the class, though some famil­iar­ity with algo­rithm analy­sis helps dis­tinctly. Fur­ther­more, a stu­dent who knows com­plex analy­sis is at a great advan­tage towards the begin­ning of the sec­ond half of the course. Pro­fes­sor Sedgewick encour­ages col­lab­o­ra­tion and is one of the most orga­nized lec­tur­ers at Prince­ton, so the course ends up being acces­si­ble to any­one inter­ested in tak­ing it. He is also known to be very gen­er­ous with his final grades.
Although the “dis­crete” part of this course is con­fined to the first half, it is a course worth tak­ing. Pro­fes­sor Sedgewick loves teach­ing the class, and takes great care to ensure that the con­tent is well under­stood by every­one. Fur­ther­more, it is use­ful in sim­pli­fy­ing a num­ber of prob­lems that come up a lot in “real-life com­puter sci­ence,” and solv­ing them with the aid of the beau­ti­ful but counter-intuitive approaches aris­ing from mathematics.

Con­tact [Show]Con­tact [Hide]
Rik Sen­gupta ’12 (rsengupt[at]mit[dot]edu)