Combinatorial Reciprocity Theorems: An Invitation to Enumerative Geometric Combinatorics

Consider a combinatorially defined polynomial, like the chromatic polynomial \(f_{G}(n)\) of a graph \( G \). For each positive integer \( n \), the value of that polynomial is the number of ways to color the vertices of G so using only colors \( 1, 2,...,n \) so that adjacent vertices are of different color. (It is not difficult to prove that \( f_{G} \) is indeed a polynomial function.) However, why would we obtain anything meaningful if we plug in a negative integer into our polynomial? It turns out that plugging in -1, we get, up to sign, the number of acyclic orientations of \( G \).

This is a spectacular example of a combinatorial reciprocity theorem-- when a combinatorially defined polynomial takes combinatorially meaningful values even for negative integers. In the first chapter of this reader-friendly book, the authors announce four such theorems that they will prove later in the book. In the next three chapters, they review diverse areas they will need: partially ordered sets, polyhedral geometry, and rational generating functions. Readers familiar with one of these topics can skip that chapter without getting into trouble in the others.

Then come three advanced chapters that should be read in sequence: subdivisions, geometric aspects of partially ordered sets, and finally, hyperplane arrangements. These are at least at advanced graduate student level.

Given how diverse that list of topics is, it is not a surprise that so far readers had to scan many sources to find all these results, and now the book collects them in one place. There are plenty of exercises, though none of them have solutions. While the format of the book makes it appropriate as a textbook, the wide array of included topics makes this reviewer think that most readers will use the book as a reference manual.

Miklós Bóna is a Professor and Distinguished Teaching Scholar at the University of Florida, and the author and editor of several books. His main research interest is Enumerative Combinatorics.