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 Bn have at most degree n. We show that this bound is sharp for some revlex term orders. For (m×n)-transportation polytopes, a similar result holds: they have Gröbner bases of at most degree ⌊mn/2⌋. We construct a family of examples, where this bound is sharp.
Résumé. Nous démontrons que les idéaux toriques des polytopes de flot sont engendrés par un ensemble de degré 3. Cela a été conjecturé par Diaconis et Eriksson pour le cas particulier du polytope de Birkhoff. Notre preuve utilise une méthode de subdivision par hyperplans, développée par Haase et Paffenholz. Il est bien connu que les bases de Gröbner revlex réduite du polytope de Birkhoff Bn sont au plus de degré n. Nous démontrons que cette borne est optimale pour quelques ordres revlex. Pour les polytopes de transportation de dimension (m×n), il existe un résultat similaire : leurs bases de Gröbner sont au plus de degré ⌊mn/2 ⌋. Nous construisons une famille d'exemples pour lesquels cette borne est atteinte.
Resumen. Demostramos que los ideales tóricos de politopos de flujo se generan en grado 3. Esto fue conjeturado por Diaconis y Eriksson para el caso especial del politopo de Birkhoff. Nuestra demostración utiliza un método de subdivisión de hiperplanos desarrollado por Haase y Paffenholz. Se sabe que las bases de Gröbner revlex reducidas de los ideales tóricos del politopo de Birkhoff Bn tienen como máximo grado n. Se demuestra que este límite es tight en algunos ordenes de termines revlex. Para politopos de transporte (m×n), existe un resultado similar: tienen bases de Gröbner de máximo grado ⌊mn/2 ⌋. Construimos una familia de ejemplos, mostrando que este límite es tight.