Combinatorial Reciprocity Theorems

An undergraduate seminar during the fall of 2018.

A basic problem in combinatorics—in fact, probably in life!—is to count: how many objects are there of a particular shape, perhaps limited by a parameter \(n\)? Varying the parameter \(n\) gives a sequence of non-negative integers which can be packaged into a counting function. Remarkably often, these counting functions turn out to be restrictions of polynomials, or other nice functions defined on the entire set of integers, to the non-negative ones. One might ask: do evaluations of the counting function at negative integers mean something? Again, remarkably often, these negative evaluations turn out to count some sort of “dual” object. Such an answer is called a combinatorial reciprocity theorem.

With combinatorial reciprocity theorems as our guiding stars, this seminar is an introduction to the beautiful landscape of enumerative and geometric combinatorics. The gadgets and tools we will find at hand are those of modern algebraic combinatorics, such as the theory of partially ordered sets, Möbius functions, and generating functions. The local wildlife consist primarily of of polyhedra, polytopes, cones, and hyperplane arrangements, all of which have been marvelled since the ancients.

Prerequisites, Format, Expectations, etc.

This seminar should be accessible to one with a good background in linear algebra.

Beyond the mathematical content, these seminars are really about communicating mathematics. This primarily means two things for me: First, the small seminar environment is a perfect place to develop skills and a sense of comfort in speaking and presenting mathematics. Thus the seminar consists mostly of lectures by the attendees. Second, I would like to try to give direct feedback on mathematical writing, so expect an occasional problem set which, in addition to having fun with the mathematical objects at hand, is a time to think about how to write mathematics.

References

Our primary reference is a beautiful new book by Mathias Beck and Raman Sanyal:

The idea of a combinatorial reciprocity theorem was probably first formalized by Richard Stanley in a 1974 paper where he thought deeply about certain algebraic identities amongst counting functions. His original paper is not an easy read, but it’s good to know where your roots lie.

Along the way, we are going to pick up some tools from algebraic and enumerative combinatorics. A classic reference in this area is Stanley’s books on enumerative combinatorics, only the first of which should be necessary.

A large part of our adventure will be centred around polytopes, triangulations, and other topics in discrete geometry. I think the delightful book by Mathias Beck and Sinai Robins on lattice point enumeration and Ehrhart theory should suffice for most of our purposes.

For more on discrete geometry, here are three classics:

Schedule

We meet Monday and Wednesdays in Mathematics Room 528 between 4:30PM and 5:30PM.

09/04
Organization.
09/07
Raymond Cheng
Introduction, Colourings, and Acyclic Orientations of Graphs
09/10
No Seminar
Raymond in Italy
09/12
No Seminar
Raymond in Italy
09/17
Raymond Cheng
Posets and Order Polynomials
09/19
Raymond Cheng
Polygons and Ehrhart Functions
09/24
Benjamin Foutty
Posets, Möbius Functions, and Order Polynomial Reciprocity
09/26
Benjamin Mazel
Principle of Inclusion-Exclusion, and Möbius Functions
10/01
Allison Clark
Polyhedra, Polytopes, and Cones
10/03
Hsin Pei Toh
Minkowski--Weyl Theorem and Faces of Polyhedra
10/08
Justin Whitehouse
Construction of the Euler Characteristic on Polytopes
10/10
Junho Won
Euler Characteristics and Möbius Functions
10/15
Raymond Cheng
Subdivisions of Polyhedra
10/17
Ethan Kestenberg
Brief on Generating Functions
10/22
Yoon Kim
Hyperplane Arrangements and Zaslavsky's Theorem
10/24
Benjamin Foutty
Ehrhart Functions and Integer-Point Transforms
10/03
Junho Won
Stanley Reciprocity
10/31
Ethan Kestenberg
Ehrhart's Reciprocity and Theorem
11/05
No Seminar
Think About Voting!
11/07
Justin Whitehouse
Möbius Functions of Subdivisions and Ehrhart--Macdonald Reciprocity
11/12
Allison Clark
Order Cones and Order Polytopes
11/14
Benjamin Mazel
Subdivisions of Order Polyhedra
11/19
Hsin Pei Toh
Combinatorics of Permutations
11/21
No Seminar
Happy Thanksgiving!
11/26
No Seminar
11/28
Yoon Kim
Regions of Hyperplane Arrangements
12/03
Raymond Cheng
Pretty Things
12/05
Raymond Cheng
More Pretty Things
12/10
Raymond Cheng
Conclusion and Parting Words