Computational Discrete Mathematics




Course Information Lecturers: Chien-Chung Huang, Ariel Levavi

Classroom: Rotunda, MPI 3rd Floor.

Class: Monday, 4-6PM, Wednesday, 2-4PM.

Office Hours: Tuesday, 2-3PM, Chien-Chung; Thursday, 2-3PM, Ariel.

Description: This course is intended for graduate students and/or senior undergraduate students. It consists of three-hour lecture and another one-hour problem solving session. It covers topics that we deem are of fundamental importance for students interested in pursuing a career in theory/algorithms. We also do not neglect to balance the materials so that students will find them entertaining.

The only prerequisite is basic knowledge of algorithms and the love of mathematics.

You can find the syllabus here


First Week: We talked about Hall's marriage theorem and Birkhoff theorem. We also gave a short introduction about the stable marriage problem. You can find the slides here

Second Week : We presented Berge's theorem, Konig's theorem and Egervary's theorem. We gave out the first homework. In this link there is a brief summary of the materials we have covered so far.

Third Week : We explained the Hungarian method and Dilworth's theorem. Here are more notes and summaries.

Fourth Week : Max-flow-min-cut theorem is presented along with quite a few applications. Here are the class notes. The second homework is here.

Fifth Week : Fulkerson's chain decomposition algorithm, Sperner's theorem, LYM inequality, symmetric chain decomposition, Bollobas' theorem are presented.

Sixth Week : Erdos-Ko-Rado theroem is presented. Several matrix decomposition theorems based on circulations are also discussed in class. We gave out the third homework. The class notes are here.

Seventh Week : Hoffman's circulation theorem and min-flow-max-cut theorem are presented.

Eighth Week : Baranyai's theorem and push-relabel algorithm are presented. The fourth homework is given out.

Ninth Week : Ordinary generating functions are presented with applications on Stirling numbers of the second kind and Bell numbers. Here are more notes and summaries.

Tenth Week : We discussed exponential generating functions and presented the Fundamental Lemma of Labeled Counting and the exponential formula. The fifth homework is posted.

Eleventh Week : We used the Exponential Formula and the Lagrange Inversion Formula to prove Cayley's Formula, and introduced the topic of Ramsey's Numbers for Graphs. New course notes are here.

Twelfth Week : We proved Ramsey's Theorem for graphs and a specific case of Ramsey's Theory for sets. We also applied Ramsey's theorem to prove Schur's Theorem, and introduced the Erdos-Szekeres Theorem for convex polygons. The final homework is given out.

Thirteenth Week : On Monday we presented Winkler's theorem (on squashed cube conjecture). On Wednesday, we proved the 5-Color Theorem and Cayley's Formula using the Prufer Code. The last class notes are here. And this is the proof of Brook's theorem from textbook.

Fourteenth Week : We talk about selected topics in stable matching and in pegging numbers.


More Courses of the Algorithms and Complexity Group