Matthias Lenz - Toric Ideals of Flow Polytopes

dmtcs:2837 - Discrete Mathematics & Theoretical Computer Science, January 1, 2010, DMTCS Proceedings vol. AN, 22nd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2010) - https://doi.org/10.46298/dmtcs.2837
Toric Ideals of Flow PolytopesArticle

Authors: Matthias Lenz 1

We show that toric ideals of flow polytopes are generated in degree $3$. This was conjectured by Diaconis and Eriksson for the special case of the Birkhoff polytope. Our proof uses a hyperplane subdivision method developed by Haase and Paffenholz. It is known that reduced revlex Gröbner bases of the toric ideal of the Birkhoff polytope $B_n$ have at most degree $n$. We show that this bound is sharp for some revlex term orders. For $(m \times n)$-transportation polytopes, a similar result holds: they have Gröbner bases of at most degree $\lfloor mn/2 \rfloor$. We construct a family of examples, where this bound is sharp.


Volume: DMTCS Proceedings vol. AN, 22nd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2010)
Section: Proceedings
Published on: January 1, 2010
Imported on: January 31, 2017
Keywords: Toric ideal,Flow polytope,Transportation polytope,Gröbner basis,Markov basis,[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO],[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

Consultation statistics

This page has been seen 174 times.
This article's PDF has been downloaded 194 times.