Math 462, Combinatorial Theory II

Winter 2018

• Course Information

• Syllabus and Homework Guidelines

•  Link to the Math 461 notes.
  

• Lecture Notes

• Lecture 1, Intro and Kruskal's Algorithm: existence (covering 10.3)
• Lecture 2, Kruskal's algorithm: minimality (finishes 10.3)
• Lecture 3, adjacency matrices (10.4)
• Lecture 4, matrix-tree theorem; coloring and chromatic number (10.5 and 11.1)
• Lecture 5, Chromatic numbers; bipartite graphs (11.1, 11.2)
• Lecture 6, Bipartite graphs; matchings (11.2, 11.3)
• Lecture 7, Matchings (11.3)
• Lecture 8, Matchings: Hall's Theorem (11.3)
• Lecture 9, Maximum Matchings; Multiple Colors (11.3, 11.4)
• Lecture 10, Chromatic number; Bounds; Chromatic polynomial (11.4)
• Lecture 11, Planar Graphs (12.1)
• Lecture 12, Planar graphs and convex polyhedra (12.1, 12.2)
• Lecture 13, Planar graphs, convex polyhedra, and duality (12.2)
• Lecture 14, Convex polyhedra, Platonic solids, color maps (12.2, 12.3)
• Lecture 15, Ramsey Theory (13.1)
• Lecture 16, More Ramsey Theory (13.1, 13.2)
• Lecture 17, Applications of Ramsey Theory (13.3)
• Lecture 18, Probabilistic Method, I (15.1)
• Lecture 19, Probabilistic Method, II (Ramsey Numbers) (15.2)
• Lecture 20, Probabilistic Method, III (Conditional Probability) (15.3)
• Lecture 21, Probabilistic Method, IV (Expectation) (15.4)
• Lecture 22, Partially Ordered Sets (posets) (16.1)
• Lecture 23, Partial Orderings: Mirsky's Theorem (16.1)
• Lecture 24, Partial Orderings: Dilworth's Theorem, applications (16.1)

• Homework

• Homework 1, due January 12
• Homework 2, due January 19
• Homework 3, due January 26
• Homework 4, due February 2
• MIDTERM-LIKE QUESTIONS, to be discussed in class 02/05 and in review session 02/06
• SOLUTIONS to the midterm-like questions
• MIDTERM SOLUTIONS
• Homework 5, due February 16
• Homework 6, due February 23
• Homework 7, due March 2
• FINAL REVIEW QUESTIONS, to be discussed in class 03/09 and in review session 03/12
• SOLUTIONS to the Final Review Questions

• Exams
  

• Midterm       Wednesday, February 7 (during class time, in LOW 205)
  

• Final             Wednesday, March 14  (2:30am-4:20pm, in LOW 205)
  

• Combinatorial Links  (list under construction, valid for 461 and 462) :

• 19 Proofs of the Euler Theorem
  
• Catalan numbers (and the many combinatorial objects they count), courtesy of Richard Stanley
  
• Graph coloring
• Graph theory tutorials
• Jiri Matousek's and Jan Vondrak's notes on the probabilistic method (the output is in 2pages-per-sheet format)
• An easy introduction to generating functions
• A few "nice" generating functions from Mathworld (which, incidentally, is a good resource for all things mathematical)