A Plethora of Polynomials: A Toolbox for Counting Problems

Abstract

A wide variety of problems in combinatorics and discrete optimization depend on counting the set S of integer points in a polytope, or in some more general object constructed via discrete geometry and first-order logic. We take a tour through numerous problems of this type. In particular, we consider families of such sets S_t depending on one or more integer parameters t, and analyze the behavior of the function $f(t)=\left|S_t\right|$. In the examples that we investigate, this function exhibits surprising polynomial-like behavior. We end with two broad theorems detailing settings where this polynomial-like behavior must hold. The plethora of examples illustrates the framework in which this behavior occurs and also gives an intuition for many of the proofs, helping us create a toolbox for counting problems like these.

MSC::

• Primary 52C07
• Secondary 05A15

ACKNOWLEDGMENT

We thank John Goodrick, Danny Nguyen, and Chris O’Neill for useful discussions as we were writing this paper. We also appreciate the reviewers’ careful reading and helpful comments.

Additional information

Notes on contributors

Tristram Bogart

TRISTRAM BOGART received his Ph.D. from the University of Washington in 2007. After post docs at Queen’s University and MSRI/San Francisco State University, he moved to Los Andes University in Bogotá, Colombia, where he is now an Associate Professor of Mathematics.

Kevin Woods

KEVIN WOODS received his Ph.D. from the University of Michigan in 2004. After a post doc at the University of California, Berkeley, he moved to Oberlin College in 2006, and he is now a Professor of Mathematics there. He is happiest when he is with his dogs or is taking long walks, but he is sad that his dogs cannot keep up on these long walks.