A plethora of polynomials: a toolbox for counting problems

DOI10.1080/00029890.2022.2010487MaRDI QIDQ5067476zbMATH OpenOpenAlexFDO

Authors

Publication date 1 April 2022

Published in The American Mathematical Monthly (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2012.12976

zbMATH Keywords

counting problemsinteger points in a polytope

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Lattice points in specified regions (11P21) Lattices and convex bodies in (n) dimensions (aspects of discrete geometry) (52C07)

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)=|S_t|$. 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.

Recommendations

• The complexity of generating functions for integer points in polyhedra and beyond
• The many aspects of counting lattice points in polytopes
• Computing the Continuous Discretely
• Integer points in polyhedra
• scientific article; zbMATH DE number 1405493

Cites work

• A \(q\)-queens problem. V: Some of our favorite pieces: queens, bishops, rooks, and nightriders
• A parametric version of LLL and some consequences: parametric shortest and closest vector problems
• Complexity of the Frobenius problem
• Computing the Continuous Discretely
• Factorization length distribution for affine semigroups. I: Numerical semigroups with three generators
• Factorization length distribution for affine semigroups. II: Asymptotic behavior for numerical semigroups with arbitrarily many generators
• Generalized Ehrhart polynomials
• Hilbert's Tenth Problem is Unsolvable
• scientific article; zbMATH DE number 3163858 (Why is no real title available?)
• scientific article; zbMATH DE number 3408928 (Why is no real title available?)
• scientific article; zbMATH DE number 2229032 (Why is no real title available?)
• scientific article; zbMATH DE number 3101854 (Why is no real title available?)
• Inside-out polytopes
• Integer hulls of linear polyhedra and scl in families
• Integer points in polyhedra
• Newton polyhedron, Hilbert polynomial, and sums of finite sets
• On the completeness of a certain system of arithmetic of whole numbers in which addition occurs as the only operation
• On vector partition functions
• Parametric Presburger arithmetic: complexity of counting and quantifier elimination
• Parametric Presburger arithmetic: logic, combinatorics, and quasi-polynomial behavior
• Parametrizing an integer linear program by an integer
• Periodic behavior in families of numerical and affine semigroups via parametric Presburger arithmetic
• Polynômes arithmétiques et méthode des polyedres en combinatoire
• Six little squares and how their numbers grow
• The parametric Frobenius problem
• The unreasonable ubiquitousness of quasi-polynomials

This page was built for publication: A plethora of polynomials: a toolbox for counting problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5067476)