2008/01/03 by Matthias Lenz, Lenz, Matthias
Mathematics · #13P10 #14M25 #52B20 #Combinatorics (math.CO) #Commutative Algebra (math.AC) #FOS: Mathematics #math.AC #math.CO #msc:13P10 #msc:14M25 #msc:52B20
paper · pdf · doi:10.48550/arxiv.0801.0495
Withdrawn due to an error in the proof of the Main Theorem
arxiv created 2011/03/04 · arxiv updated 2011/03/07
A referee found an error in the proof of the Main Theorem ("toric ideals of flow polytopes are generated in degree 3") that we could not fix. More precisely, the proof of Lemma 4.2.(ii) is incorrect. The results on Gröbner bases are untouched by this. ----- 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 \lfloor mn/2\rfloor. We construct a family of examples, where this bound is sharp.