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,
[Lecture 1 Notes], [Beck–Sanyal (2018), §§0,1.1].
09/10
No Seminar,
Raymond in Italy,
Suggested reading on enumeration: [Beck–Robins (2015), Chapter 1], [Stanley (2012), §§1.1–1.2].
09/12
No Seminar,
Raymond in Italy,
Suggested reading on polytopes: [Beck–Robins (2015), Chapter 2], [Ziegler (1995), Lecture 0].
09/17
Raymond Cheng,
Posets and Order Polynomials,
[Beck–Sanyal (2018), §1.3].
09/19
Raymond Cheng,
Polygons and Ehrhart Functions,
[Beck–Sanyal (2018), §1.4].
09/24
Benjamin Foutty,
Posets, Möbius Functions, and Order Polynomial Reciprocity,
[Beck–Sanyal (2018), §§2.1–2.2], [Stanley (2012), §§3.1,3.6].
09/26
Benjamin Mazel,
Principle of Inclusion-Exclusion, and Möbius Functions,
[Beck–Sanyal (2018), §§2.1,2.4], [Stanley (2012), §§3.7–3.8].
10/01
Allison Clark,
Polyhedra, Polytopes, and Cones,
[Beck–Robins (2015), §§2.1–2.3], [Beck–Sanyal (2018), §§3.1–3.2], [Ziegler (1995), Lecture 1].
10/03
Hsin Pei Toh,
Minkowski–Weyl Theorem and Faces of Polyhedra,
[Beck–Sanyal (2018), §§3.2–3.3], [Ziegler (1995), Lecture 2].
10/08
Justin Whitehouse,
Construction of the Euler Characteristic on Polytopes,
[Beck–Sanyal (2018), §3.4].
10/10
Junho Won,
Euler Characteristics and Möbius Functions,
[Beck–Sanyal (2018), §§3.4–3.5].
10/15
Raymond Cheng,
Subdivisions of Polyhedra,
[Beck–Sanyal (2018), §5.1].
10/17
Ethan Kestenberg,
Brief on Generating Functions,
[Beck–Sanyal (2018), §§4.1–4.3], [Stanley (2012), §1.1–1.2].
10/22
Yoon Kim,
Hyperplane Arrangements and Zaslavsky’s Theorem,
[Beck–Sanyal (2018), §§3.5–3.6].
10/24
Benjamin Foutty,
Ehrhart Functions and Integer-Point Transforms,
[Beck–Robins (2015), §§3.2–3.5], [Beck–Sanyal (2018), §§4.6–4.7].
10/29
Junho Won,
Stanley Reciprocity,
[Beck–Sanyal (2018), §4.8].
10/31
Ethan Kestenberg,
Ehrhart’s Reciprocity and Theorem,
[Beck–Sanyal (2018), §§4.6–4.8].
11/05
No Seminar.
Think About Voting!
11/07
Justin Whitehouse,
Möbius Functions of Subdivisions and Ehrhart–Macdonald Reciprocity,
[Beck–Sanyal (2018), §§3.5,5.2].
11/12
Allison Clark,
Order Cones and Order Polytopes,
[Beck–Sanyal (2018), §§6.1,6.3].
11/14
Benjamin Mazel,
Subdivisions of Order Polyhedra,
[Beck–Sanyal (2018), §§6.2–6.3].
11/19
Hsin Pei Toh,
Combinatorics of Permutations,
[Beck–Sanyal (2018), §6.4], [Stanley (2012), §1.3–1.5].
11/21
No Seminar,
Happy Thanksgiving!
11/26
No Seminar,
11/28
Yoon Kim,
Regions of Hyperplane Arrangements,
[Beck–Sanyal (2018), §7.2].
12/03
Raymond Cheng.
Pretty Things.
12/05
Raymond Cheng.
More Pretty Things.
12/10
Raymond Cheng.
Conclusion and Parting Words.