Column-Convex Matrices, G-Cyclic Orders, and Flow Polytopes

We study polytopes defined by inequalities of the form ∑ _i∈Iz_i≤ 1 for I⊆ [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 volumes of these flow polytopes are given by the number of upper (or lower) G-cyclic orders defined by the graphs 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^∗ -polynomial of consecutive coordinate polytopes, we give a combinatorial formula for the h^∗ -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^∗ -polynomial.