Title: Approximately Counting Flows via Generating Function Optimization
| Speaker: | Jonathan Leake |
| Affiliation: | University of Waterloo |
| Location: | MC 5479 |
Abstract: In this talk, we will present recent new lower bounds on the number of non-negative integer flows on a directed acyclic graph with specified total vertex flows (or equivalently, the number of lattice points of a given flow polytope, or the coefficients of the A-type Kostant partition function). We will also give a sketch of the proof, which involves three main parts: (1) prove a certain log-concavity property of the associated multivariate generating function, (2) prove bounds on the coefficients in terms of an associated optimization problem, and (3) dualize the optimization problem to obtain the desired lower bounds. If time permits, we will also briefly discuss other applications of this technique, including to approximating Kostka numbers and to the traveling salesperson problem. Joint work with Alejandro Morales, and with Petter Brändén and Igor Pak.