Column convex matrices, $G$-cyclic orders, and flow polytopes

Abstract

We study polytopes defined by inequalities of the form ${\sum }_{i\in I}{z}_i\le 1$ for $I\subseteq [d]$ and nonnegative $z_i$ where the inequalities can be reordered into a matrix inequality involving a column-convex $\{0,1\}$-matrix. These generalize polytopes studied by Stanley, and the consecutive coordinate polytopes of Ayyer, Josuat-Vergès, and Ramassamy. We prove an integral equivalence between these polytopes and flow polytopes of directed acyclic graphs $G$ with a Hamiltonian path, which we call spinal graphs. We show that the volume of these flow polytopes is the number of extensions of a set of partial cyclic orders defined by the graph $G$. As a special case we recover results on volumes of consecutive coordinate polytopes. We study the combinatorics of $k$-Euler numbers, which are generalizations of the classical Euler numbers, and which arise as volumes of flow polytopes of a special family of spinal graphs. We show that their refinements, Ramassamy's $k$-Entringer numbers, can be realized as values of a Kostant partition function, satisfy a family of generalized boustrophedon recurrences, and are log concave along root directions. Finally, via our main integral equivalence and the known formula for the $h^{\ast }$-polynomial of consecutive coordinate polytopes, we give a combinatorial formula for the $h^{\ast }$-polynomial of flow polytopes of non-nested spinal graphs. For spinal graphs in general, we present a conjecture on upper and lower bounds for their $h^{\ast }$-polynomial.

33 pages, 12 figures, 2 tables