Course MAT377

Combinatorial Mathematics

Combinatorics is the study of enumeration and structure of discrete objects. These structures are widespread throughout mathematics, including geometry, topology and algebra, as well as computer science, physics, and optimization. This course will give an introduction to modern techniques in the field, and how they relate to objects such as polytopes, permutations, and hyperplane arrangements. Current work and open problems will also be discussed.

Topics

Course Outline:

I. Introduction to Polytopes

  • Euler's forumula and applications
  • Gram's theorem
  • Steinitz's theorems for 3-dimensional poltopes
  • Cauchy's theorem on rigidity and the Bellows theorem
  • Hilbert's Third Problem on Scissors Congruence

II. Basic Enumeration

  • Generating functions
  • Fibonacci numbers and compositions
  • Binomial theorem and lattice paths
  • Andre reflection theorem and the Catalan numbers
  • Stirling numbers and Bell numbers
  • Permutations and permutation statistics
  • The 15 game and Rubik's cube
  • q-analogues, juggling and the affine Weyl group
  • Principle of Inclusion and Exclusion
  • The Twelvefold way

III. Lectures in Geometric and Topological Combinatorics

  • Chromatic polynomial, acyclic orientations and hyperplane arrangements
  • Valuations and the characteristic polynomial
  • Sperner's lemma, Brouwer's fixed point theorem and Frobenius-Perron
  • The Law of Aboav-Weaire in material science
  • Mixed volumes, Eulerian numbers and Bernstein's theorem
  • Heawood's bound on the chromatic numbers of surfaces
  • Probabilistic approach to permutations

IV. Matchings and Tree Enumeration

  • Three proofs of Cayley's theorem
  • Matrix tree theorem and electrical networks
  • Hall's Marriage Theorem and the Birkhoff polytope
  • The Stable Marriage Theorem and distributive lattices

V. Partially Ordered Sets

  • Dilworth's theorem
  • LYM inequality, Sperner's Lemma, Greene-Kleitman chain decomposition
  • Mobius function
  • Fundamental theorem of finite distributive lattices

VI. Advanced Topics in Polytopes

  • Bruggesser-Mani line shellings
  • Euler-Poincare and Dehn-Sommerville relations
  • Cyclic polytopes and the upper bound theorem
  • Kruskal-Katona theorem and the g-theorem
  • Pick's theorem and Ehrhart theory

 

Description of classes

Grading:

Bi-weekly Problem Sets           30% of course grade
Take-home Midterm Exam       30% of course grade
Take-home Final Exam             30% of course grade

Notes

There is no formal text for the course. Course notes will be made available to the students as well as supplementary handouts.