## 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.

### Funding

This work was supported by the American Institute of Mathematics through their SQuaRE program. We are very appreciative of their support and funding which made this research collaboration possible. We thank Carolina Benedetti and Pamela E. Harris for fruitful discussions throughout the process. We thank Arvind Ayyer, Matthieu Josuat-Vergès, and Sanjay Ramassamy for telling us about [3 ]. We also thank the anonymous referees for their kind comments and suggestions to improve the latest version of the article. R. S. González D’León is very grateful with the Escuela de Ciencias Exactas e Ingeniería of Universidad Sergio Arboleda and the Departamento de Matemáticas of Pontificia Universidad Javeriana as part of this work was developed under their support. C.R.H. Hanusa was partially supported by a PSC-CUNY Award, jointly funded by The Professional Staff Congress and The City University of New York. A.H. Morales was partially supported by NSF Grant DMS-1855536, M. Yip was partially supported by Simons Collaboration Grant 429920. This work was supported by the American Institute of Mathematics through their SQuaRE program. We are very appreciative of their support and funding which made this research collaboration possible. We thank Carolina Benedetti and Pamela E. Harris for fruitful discussions throughout the process. We thank Arvind Ayyer, Matthieu Josuat-Vergès, and Sanjay Ramassamy for telling us about []. We also thank the anonymous referees for their kind comments and suggestions to improve the latest version of the article. R. S. González D’León is very grateful with the Escuela de Ciencias Exactas e Ingeniería of Universidad Sergio Arboleda and the Departamento de Matemáticas of Pontificia Universidad Javeriana as part of this work was developed under their support. C.R.H. Hanusa was partially supported by a PSC-CUNY Award, jointly funded by The Professional Staff Congress and The City University of New York. A.H. Morales was partially supported by NSF Grant DMS-1855536, M. Yip was partially supported by Simons Collaboration Grant 429920.

Funders | Funder number |
---|---|

Escuela de Ciencias Exactas e Ingeniería of Universidad Sergio Arboleda | |

Simons Collaboration | 429920 |

National Science Foundation Arctic Social Science Program | DMS-1855536 |

American Institute of Mathematics Structured Quartet Research Ensembles | |

City and State of New York, City University of New York Research Foundation | |

Professional Staff Congress and City University of New York | |

Pontificia Universidad Javeriana |

## 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