Geodesic
Toric Ideals of Flow Polytopes
Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AN, 22nd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2010), DMTCS Proceedings vol. AN, 22nd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2010) (2010) Cet article a éte moissonné depuis la source Episciences

Voir la notice de l'article

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. 
@article{DMTCS_2010_special_259_a32,
     author = {Lenz, Matthias},
     title = {Toric {Ideals} of {Flow} {Polytopes}},
     journal = {Discrete mathematics & theoretical computer science},
     year = {2010},
     volume = {DMTCS Proceedings vol. AN, 22nd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2010)},
     doi = {10.46298/dmtcs.2837},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2837/}
}
TY  - JOUR
AU  - Lenz, Matthias
TI  - Toric Ideals of Flow Polytopes
JO  - Discrete mathematics & theoretical computer science
PY  - 2010
VL  - DMTCS Proceedings vol. AN, 22nd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2010)
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2837/
DO  - 10.46298/dmtcs.2837
LA  - en
ID  - DMTCS_2010_special_259_a32
ER  - 
%0 Journal Article
%A Lenz, Matthias
%T Toric Ideals of Flow Polytopes
%J Discrete mathematics & theoretical computer science
%D 2010
%V DMTCS Proceedings vol. AN, 22nd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2010)
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2837/
%R 10.46298/dmtcs.2837
%G en
%F DMTCS_2010_special_259_a32
Lenz, Matthias. Toric Ideals of Flow Polytopes. Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AN, 22nd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2010), DMTCS Proceedings vol. AN, 22nd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2010) (2010). doi: 10.46298/dmtcs.2837

Cité par Sources :