Homepage of APM 5669

APM 5669, Winter 2016

Office Hours: See handout.

Lectures

Jan 5: Review of basic material of APM 563.

Jan 7: Chromatic polynomials, deletion and contraction, proof of Brooks' Theorem. (If you are interested in a different proof. See here.)

Jan 12: Matrix-Tree Theorem, deletion and contraction proof. Cayley's Formula.

Jan 14: Second proof of Matrix-Tree Theorem: Doron Zeilberger's awesome combinatorial proof here) Two more proofs of Cayley's Formula via generating functions, enumeration of permutations with respect to cycle decomposition, enumeration of functional digraphs with respect to cycle decomposition.

Jan 19: Kuratowski's Theorem (Thomassen's proof), Wagner's Theorem.

Jan 21: Dirac's Theorem, Ore's Theorem, Bondy-Chvatal Theorem, r-spanning equi-cyclable.

Jan 26: r-spanning equi-cyclable, edge coloring, Vizing's Theorem.

Jan 28: Vizing's Theorem, "total" coloring.

Feb 2: Relationship between transitivity and connectivity both vertex and edge versions. Mader's Theorem.

Feb 4: Relationship between transitivity and connectivity both vertex and edge versions. Watkins' Theorem.

Feb 9: Total coloring.

Feb 11: Total coloring of cactus, Menger's Theorem directed, arc and vertex versions.

Feb 16: Submodular function in graph theory: Hall's Theorem, Menger's Theorem directed arc version.

Feb 18: Submodular function in graph theory: Hall's Theorem, Menger's Theorem directed arc version.

Mar 1: Submodular function in graph theory: Edmonds' Theorem of disjoint spanning arborescences (common root), Frank's Theorem of disjoint spanning arborescences.

Mar 3: Submodular function in graph theory: Tutte's Theorem of disjoint spanning trees.

Mar 8: Guest Lecture by Professor Steffy.

Mar 10: Submodular function in graph theory: Mader's Splitting-Off Theorem for digraphs. Frank's digraph edge augmentation theorem.

Mar 15: Submodular function in graph theory: Lovasz' Splitting-Off Theorem for graphs. Cai and Sun edge augmentation theorem, Frank's algorithm.

Mar 17: Submodular function in graph theory: Nash-Williams Weak Orientation Theorem, successive augmentation problem.

Mar 22: Tutte's Theorem of perfect matchings, Tutte-Berge Formula.

Mar 24: Alternate proof of Tutte's Theorem, the equivalency of Tutte's Theorem and Tutte-Berge Formula.

Mar 29: Matching preclusion and conditional matching preclusion of bipartite graphs.

Mar 31: Sufficient conditions for maximally matched, super matched, conditionally maximally matched and conditionally super matched for bipartite graphs.

Apr 5: Plesnik's Theorem, sufficient conditions for maximally matched, super matched, conditionally maximally matched and conditionally super matched for (not necessarily) bipartite) graphs.

Apr 7: Matching preclusion and conditional matching preclusion of classes of interconnection Networks.

Apr 12: Surface areas of star graphs.

Apr 14: Special office hour.