0

(

ratings

)

1

students

Created by:

Profile Photo

Last updated:

December 24, 2022

Duration:

Unlimited Duration

FREE

This course includes:

Unlimited Duration

Badge on Completion

Certificate of completion

Unlimited Duration

Description

This course covers the applications of algebra to combinatorics.

Topics include enumeration methods, permutations, partitions, partially ordered sets and lattices, Young tableaux, graph theory, matrix tree theorem, electrical networks, convex polytopes, and more.

Course Curriculum

  • Catalan numbers: drunkard’s walk problem, generating function, recurrence relation Unlimited
  • Catalan numbers (cont.) Unlimited
  • Pattern avoidance in permutations Unlimited
  • Frobenius-Young identity. Schensted correspondence. Unlimited
  • Proof of the hook-length formula based on a random hook walk Unlimited
  • Hook walks (cont.). Linear extensions of posets Unlimited
  • q-factorials and q-binomial coefficients Unlimited
  • Grassmannians over finite fields: Gaussian elimination and row-reduced echelon form Unlimited
  • Sets and multisets. Statistics on permutations: inversions, cycles, descents Unlimited
  • Statistics on permutations (cont.). Unlimited
  • Stirling numbers (cont.) Unlimited
  • Eulerian numbers Unlimited
  • Posets and lattices. Boolean lattice. Partition lattice. Young’s lattice Unlimited
  • Distributive lattices. Birkhoff’s fundamental theorem for finite distributive lattices Unlimited
  • Sperner’s property. Symmetric chain decompositions. Unlimited
  • Greene’s theorem vs Schensted correspondence. Up and down operators. Differential posets Unlimited
  • Differential posets (cont.). Fibonacci lattice Unlimited
  • Proof of unimodality of Gaussian coefficients (cont.). Unlimited
  • Partition theory (cont.). Unlimited
  • Partition theory (cont.). Combinatorial proof of Jacobi’s triple product identity. Unlimited
  • Two combinatorial proofs of Cayley’s formula Unlimited
  • Matrix Tree Theorem. Spanning trees. Unlimited
  • Matrix Tree Theorem (cont.). Unlimited
  • Proof of Matrix Tree Theorem using Cauchy-Binnet formula. Unlimited
  • Proof of Directed Matrix Tree Theorem based on induction Unlimited
  • Proof of Directed Matrix Tree Theorem via the Involution Principle. Unlimited
  • Electrical networks (cont.). Unlimited
  • Eulerian cycles in digraphs and B.E.S.T. theorem Unlimited
  • Parking functions and tree inversion polynomials Unlimited
  • Pascal triangle. Bernoulli numbers. Unlimited
  • Lindstrom-Gessel-Viennot lemma and Lindstrom Theorem Unlimited
  • Proof of Lindstrom-Gessel-Viennot lemma. Unlimited
  • MacMahon Proposition. Rhombus tiling. Domino tiling. Unlimited
  • Plane partitions. Symmetric polynomials Unlimited

About the instructor

5 5

Instructor Rating

1

Reviews

1520

Courses

1913

Students

Profile Photo
Massachusetts Institute of Technology