Totally unimodular polytopes get improved lattice point counts
Log-concavity and Approximate Counting for Totally Unimodular Polytopes
Discrete Mathematics
Summary
Counting the number of integer points inside complex shapes called totally unimodular polytopes is hard but important in math and computer science. The authors found a better way to give a guaranteed lower bound on that count, which helps estimate the number more efficiently. They used a special kind of polynomial that behaves nicely (log-concave) and confirmed a previous mathematical guess. Their method also leads to a new algorithm that can quickly approximate how many points there are, useful for various counting problems.
What this means in practice
- •For operations research teams: Efficiently approximate integer solutions in optimization problems involving unimodular constraints to improve solution bounds and performance.
- •For network design engineers: Estimate feasible integer flows in network routing modeled by totally unimodular polytopes to assist with capacity planning.
Authors
Jonathan Leake, Maryam Mohammadi Yekta
Abstract
We present a new lower bound on the number of lattice points of all totally unimodular polytopes, generalizing previous lower bounds on contingency tables, integer flows, and beyond. Our bound is based on the Gurvits capacity convex optimization problem, and thus our result implies an efficient deterministic algorithm for approximate counting of the lattice points up to an explicit exponential factor. We achieve our bounds by showing that the associated generating polynomials fit into a new general class of log-concave polynomials called VLC ("variable-wise log-concavity''). This also implies a conjecture of Ferroni and Higashitani on the evaluations of the Ehrhart polynomials of unimodular polytopes. The essential ingredient for these results is the resolution of Barvinok's log-concavity conjecture for contingency tables on lines, which was proven using ChatGPT 6 Astra. We conjecture a generalization of Barvinok's conjecture, which we believe will lead to stronger and more general bounds.