Flow polytope volume bounds via polynomial capacity
- Jonathan Leake (TU Berlin, Berlin, Germany)
Polynomial capacity has been used in the past 20 years to obtain lower bounds on various combinatorial quantities, including the permanent, the mixed discriminant, matchings of a graph, and the intersection of two matroids (to name a few). In joint work with Petter Brändén and Igor Pak, we have recently used capacity to obtain improved lower bounds on the number of contingency tables with given marginals. Contingency tables can be viewed as the lattice points of transportation polytopes and flow polytopes more generally, and so these lower bounds imply volume lower bounds for such polytopes. In this talk, we state these bounds and discuss a few key points of their proofs.