2023/07/24 by Trandafir, Stefan
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2307.13112
The vector partition function pA associated to a d × n matrix A with integer entries is the function ℤd → ℕ defined by b → #\x ∈ ℕn : Ax = b\. It is known that vector partition functions are piecewise quasi-polynomials whose domains of quasi-polynomiality are maximal cones (chambers) of a fan called the chamber complex of A. In this article we introduce external columns and external chambers of vector partition functions. Our main result is that (up to a saturation condition) the quasi-polynomial associated to a chamber containing external columns arises from a vector partition function with k fewer equations and variables. In the case that the chamber is external -- that is, when the number of external columns in a chamber is as large as possible without being trivial -- the quasi-polynomial arises from a coin exchange problem. By exploiting this we are able to obtain a determinantal formula, characterize when the quasi-polynomial is polynomial, and show that in this case it is actually given by a negative binomial coefficient. We then apply these results to the enumeration of loopless multigraphs satisfying some degree conditions. Finally, we suggest a generalization to a result of Baldoni and Vergne for polynomials arising from chambers that we call semi-external chambers.