## Abstract

We study polytopes defined by inequalities of the form ∑ _{i}_{∈}_{I}z_{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.

Original language | English |
---|---|

Pages (from-to) | 1593-1631 |

Number of pages | 39 |

Journal | Discrete and Computational Geometry |

Volume | 70 |

Issue number | 4 |

DOIs | |

State | Published - Dec 2023 |

### Bibliographical note

Publisher Copyright:© 2023, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.

## Keywords

- Boustrophedon recursion
- Column-convex matrix
- Cyclic order
- Directed acyclic graph
- Distance graph
- Doubly-convex matrix
- Entringer number
- Euler number
- Flow polytope
- G-cyclic order
- Integral equivalence
- Integral polytope
- Kostant partition function
- Log concavity
- Partial cyclic order
- Polytope
- Spinal graph
- Springer number
- k-Entringer number
- k-Euler number
- k-Springer number
- {0 , 1}-Matrix

## ASJC Scopus subject areas

- Theoretical Computer Science
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics