Computer Science/Discrete Mathematics Seminar II

A nonnegative flow on the edges of a directed acyclic graph $G$ on the vertex set $[n]$ with netflow vector $\bf{a}=(a_1, \ldots, a_n)\in \mathbb{Z}^n$ is an assignment of nonnegative real numbers to the edges of $G$ so that at each vertex $i$ the amount of flow leaving $i$ minus the amount of flow flowing into $i$ equals $a_i$. The flow polytope $\mathcal{F}_G(\bf{a})$ associated to the directed acyclic graph $G$ on the vertex set $[n]$ and a vector $\bf{a}\in \mathbb{Z}^n$ is the set of all nonnegative flows on $G$ with the netflow vector $\bf{a}$. A natural way to analyze a convex polytope is to dissect it into smaller polytopes. We will explain how the relations of the subdivision algebra encode dissections of flow polytopes. We will prove volume and Ehrhart polynomial formulas for flow polytopes in terms of Kostant partition functions. We will also examine interesting examples of flow polytopes. Time permitting we will explain the relations of flow polytopes to order polytopes, generalized permutahedra and Schubert polynomials.