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.