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

Rafael S. González D’León, Christopher R.H. Hanusa, Alejandro H. Morales, Martha Yip

Research output: Contribution to journalArticlepeer-review

Abstract

We study polytopes defined by inequalities of the form ∑ iIzi≤ 1 for I⊆ [d] and nonnegative zi 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 languageEnglish
Pages (from-to)1593-1631
Number of pages39
JournalDiscrete and Computational Geometry
Volume70
Issue number4
DOIs
StatePublished - 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

Fingerprint

Dive into the research topics of 'Column-Convex Matrices, G-Cyclic Orders, and Flow Polytopes'. Together they form a unique fingerprint.

Cite this