Math 475 - Introduction to Combinatorics (Fall 2015)




Sep 2Sections 1.1, 1.2: Pigeonhole principle; 2.1, 2.2: Induction
Sep 4Review of functions, Section 3.1: Permutations
Sep 7Holiday
Sep 9Section 3.2: Strings / words
Sep 11Section 3.3: Choice problems; Poker probability
HW1 due
Sep 14Polynomial interpolation, Section 5.1: Compositions
Sep 16Section 5.2: Set partitions
Sep 18Sections 4.1, 4.2: Binomial theorem, multinomial theorem
HW2 due
Sep 21Section 5.3: Integer partitions
Sep 23Sections 7.1, 7.2: Inclusion-exclusion
Sep 25 Formal power series; Section 4.3: General binomial theorem
HW3 due
Sep 28Section 8.1: Solving recurrence relations
Sep 30Section 8.1: Ordinary generating functions, partitions
Oct 2Section 8.1: Catalan numbers
HW4 due
Oct 5Section 8.1: Compositions of ordinary generating functions
Oct 7Review / catchup
Oct 9Midterm 1
Oct 12Midterm review
Oct 14Section 8.2: Exponential generating functions and products
Oct 16Section 8.2: Exponential generating functions and compositions
HW5 due
Oct 19Section 9.1: Graph theory terminology; Eulerian trails
Oct 21Finish 9.1; Section 9.3: directed graphs (definitions and Theorem 9.6 only);
Section 9.2: Hamiltonian cycles
Oct 23Finish 9.2; Section 9.4: Graph isomorphisms
HW6 due
Oct 26Section 10.1: Trees
Oct 28Section 10.1: Cayley's formula for number of trees (via Prüfer encoding)
Oct 30Section 10.2: Minimum-weight spanning trees, Kruskal's greedy algorithm
HW7 due
Nov 2Section 10.3: Adjacency matrices; Section 10.4: Kirchhoff's Matrix-tree theorem
Nov 4Finish 10.4
Nov 6Section 11.1: Graph colorings, chromatic polynomials
HW8 due
Nov 9Section 11.2: Bipartite graphs (just Theorem 11.5); Section 11.3: Hall's theorem
Nov 11Review / catchup
Nov 13Midterm 2: Study guide
Nov 16Finish 11.3; Stable matchings;
Section 11.5: Tutte's theorem (just statement of Theorem 11.17)
Nov 18Section 12.1: Planar graphs, see supplementary notes
Nov 20Section 12.3: Coloring planar graphs
HW9 due
Nov 23Sperner's lemma and fair division (Sections 1,3,6,7 of handout)
Nov 25Fun applications of linear algebra to combinatorics
Nov 27Holiday
Nov 30Section 11.4: Turán's theorem
Section 13.1: Ramsey theory (graphs)
Dec 2Finish 13.1
Dec 4Section 13.2: Generalizations of Ramsey's theorem, Erdős-Szekeres theorem
HW10 due
Dec 7 Finish 13.2
Dec 9 Section 15.2: Lower bounds for Ramsey numbers
Section 15.4.2: Non-constructive (probabilistic) existence proofs
Dec 11Summary of course
Dec 14Review
HW11 due
Dec 21Final exam 2:45PM - 4:45PM, Study guide