# Toric Ideals of Flow Polytopes

Matthias Lenz

Technische Universität Berlin, Sekretariat MA 4-5, Straße des 17. Juni 136, 10623 Berlin

**Abstract.** 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.

**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 $B_n$ 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 \times n)$, il existe un résultat similaire : leurs bases de Gröbner sont au plus de degré $\lfloor mn/2 \rfloor$. 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 $B_n$ 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 \times n)$, existe un resultado similar: tienen bases de Gröbner de máximo grado $\lfloor mn/2 \rfloor$. Construimos una familia de ejemplos, mostrando que este límite es tight.

**Keywords:** Toric ideal, Flow polytope, Transportation polytope, Gröbner basis, Markov basis

## 1 Introduction

Let $G = (V, A)$ be a directed graph and $d \in \mathbb{Z}^V$, $l, u \in \mathbb{N}^A$. A flow on $G$ is a function $f: A \to \mathbb{R}_{\ge 0}$ that respects the lower and upper bounds $l$ and $u$ and satisfies the demand $d$, i. e. for every vertex $v$, the flow entering $v$ minus the flow leaving $v$ equals $d_v$. A flow polytope is the set of all flows with fixed parameters $G, d, u, l$.

An important special case are *transportation polytopes*. They can be written as sets of $(m \times n)$-matrices whose row and column sums equal some fixed positive integers.
Given a lattice polytope $P$, the relations among the lattice points in $P$ define the *toric ideal* $I_P$. Generating sets of toric ideals correspond to Markov bases that are used in statistics e. g. for sampling from the set of all contingency tables with given marginals ([2]). In particular, small generating systems that can be handled by computers are of practical interest. *Diaconis and Eriksson* ([1]) conjectured that the toric ideal of the Birkhoff polytope $B_n$ (the convex hull of all $(n \times n)$-permutation matrices) is generated in degree 3. They proved this by massive computations for $n \le 6$. For arbitrary $n \ge 4$, they showed that $I_{B_n}$ has a generating set of degree $n-1$.

*Haase and Paffenholz* ([4]) proved that the toric ideals of almost all $(3 \times 3)$-transportation polytopes and particularly the smooth ones are generated in degree 2. The only exception is the Birkhoff polytope $B_3$, whose toric ideal is generated in degree 3.

Our Main Theorem proves the Diaconis-Eriksson conjecture and generalizes the result of Haase and Paffenholz:

**Theorem 1.1 (Main Theorem)** *Toric ideals of flow polytopes are generated in degree 3.*

Toric ideals define toric varieties, which are an important class of examples in algebraic geometry. A lattice polytope $P$ is smooth if the normal fan at all vertices is unimodular. Equivalently, the corresponding projective variety $X_P$ has to be smooth. It was conjectured that if $P$ is smooth, then the defining ideal is generated by quadrics ([11, Conjecture 2.9]). The original motivation of our research was to check if this conjecture holds for flow polytopes.

In *Section 2*, we review some important definitions and theorems. In *Section 3*, we describe a method that can be used to prove degree bounds for generating sets and Gröbner bases of toric ideals: first, we choose a nice triangulation of the point set and then, we use a correspondence between Gröbner bases and triangulations established by *Sturmfels*. This hyperplane subdivision method was developed by Haase and Paffenholz in [4]. In *Section 4*, we briefly describe how the method described in *Section 3* can be used to prove our Main Theorem.

*Diaconis and Sturmfels* showed that all revlex Gröbner bases of $I_{B_n}$ are at most of degree $n$ ([2, Theorem 6.1], [10, Theorem 14.8]). Computational experiments provide evidence that this bound might be optimal ([1, Remark 9]). In *Section 5* we show that for some revlex term orders, this bound is indeed optimal. Both the bound and the examples can be generalized to $(m \times n)$-transportation polytopes: reduced Gröbner bases with respect to a certain class of term orders are at most of degree $\lfloor mn/2 \rfloor$ and we construct a family of transportation polytopes and term orders, where this bound is almost sharp.

The proofs that are missing in this extended abstract are contained in the arXiv version ([6]).

## 2 Background

In this section, we review some important definitions and theorems.

**Notation:** $\mathbb{N} = \{0, 1, 2, \dots\}$. Matrices are denoted by capital letters, vectors by bold faced small letters. Their entries are denoted by the corresponding small letters. Let $\mathbf{a} = (a_1, \dots, a_n) \in \mathbb{N}^n$. We write $\mathbf{x}^\mathbf{a}$ to denote the monomial $\prod_{i=1}^n x_i^{a_i} \in k[\mathbf{x}] = k[x_1, \dots, x_n]$.

The term *polytope* always refers to a convex lattice polytope i. e. all vertices of our polytopes are integral. For background information on polyhedral geometry and polytopes see *Schrijver's* or *Ziegler's* book [9, 12].
**Flow polytopes:** Flow polytopes (or transshipment polytopes) are the main geometric objects we are dealing with. Let $G = (V, A)$ be a directed graph and $d \in \mathbb{Z}^V$, $l, u \in \mathbb{N}^A$. Let $M_G \in \{-1, 0, 1\}^{V \times A}$ denote the vertex-arc incidence matrix of $G$.

Note that the definition of flow polytopes given in the introduction is equivalent to

$$F = F_G = F_{G,d,u,l} = \{f \in \mathbb{R}_{\ge 0}^A \mid M_G f = d, l \le f \le u\} \quad (1)$$

It is a standard fact that $M_G$ is totally-unimodular. This implies that the polytope $F$ has integral vertices.

Throughout this paper, we suppose that all our flow polytopes $F$ are homogeneous, i. e. $F$ is contained in an affine hyperplane, that does not contain the origin. If $d \ne 0$ this statement holds. Otherwise, we consider the homogenized polytope $\{1\} \times F$.

An important special case of flow polytopes are transportation polytopes. In statistics, they appear under the name 2-way contingency tables.

Let $m, n \in \mathbb{Z}_{\ge 1}$, $r \in \mathbb{Z}_{\ge 1}^m$, $c \in \mathbb{Z}_{\ge 1}^n$ be two vectors satisfying $\sum_{i=1}^m c_i = \sum_{i=1}^m r_i =: s$. The transportation polytope $T_{rc}$ is defined as

$$T_{rc} = \left\{ A \in \mathbb{R}_{\ge 0}^{m \times n} \mid \sum_{i=1}^{m} a_{ij} = c_j, \sum_{j=1}^{n} a_{ij} = r_i \right\} \quad (2)$$

The upper $((m-1) \times (n-1))$-minor of a matrix $A \in T_{rc}$ determines all other entries. Hence, the dimension of $T_{rc}$ is at most $(m-1)(n-1)$. On the other hand, $a_{ij} = r_i c_j / s$ determines an interior point, so that the dimension is exactly $(m-1)(n-1)$.

If $r = c = (1, \dots, 1)$, we obtain an important example: the Birkhoff polytope $B_n$.

**Toric ideals and Gröbner bases:** This paragraph defines toric ideals and Gröbner bases as in *Sturm-fels's book* ([10]). Let $k$ be a field and let $P \subseteq \mathbb{R}^d$ be a homogeneous lattice polytope. The set of its lattice points $\mathcal{A} = \{a_i \mid i \in I\}$ defines a semigroup homomorphism $\pi : \mathbb{N}^I \to \mathbb{Z}^d$, $u \mapsto \sum_{i \in I} u_i a_i$, which can be lifted to a ring homomorphism

$$\hat{\pi} : k[x_i \mid i \in I] \to k[t_1^{\pm 1}, \dots, t_d^{\pm 1}], \quad x_i \mapsto t^{a_i} \quad (3)$$

Its kernel is the homogeneous ideal $I_A = \langle x^u - x^v \mid \sum_{i \in I} u_i a_i = \sum_{i \in I} v_i a_i \rangle$. This ideal is called the toric ideal associated to $\mathcal{A}$ (or $P$ respectively).

A binomial $x^u - x^v \in I_A$ corresponds to a relation between points in $\mathcal{A}$. For example, for $\mathcal{A} = B_3 \cap \mathbb{Z}^{3 \times 3}$, $I_A$ is generated by the binomial that corresponds to the relation $\sum_{\det(M)=1} M = \sum_{\det(M)=-1} M$.

A total order $\prec$ on $\mathbb{N}^n$ is a term order if $a \prec b$ implies $a + c \prec b + c$ for all $a, b, c \in \mathbb{N}^n$ and the zero vector is the unique minimal element. An important example is the graded reverse lexicographic (revlex) order: $a \prec_{\text{revlex}} b$ if $\sum_i a_i < \sum_i b_i$ or $\sum_i a_i = \sum_i b_i$ and the rightmost non-zero entry in $a - b$ is positive. Note that the revlex order depends on the order of the variables.

Let $I \subseteq k[x_1, \dots, x_n]$ be an ideal and let $\prec$ denote a term order on $\mathbb{N}^n$. For $f \in k[x_1, \dots, x_n]$, let $\text{in}_\prec(f)$ denote the initial (largest) term of $f$ with respect to $\prec$. A finite set $\mathcal{G} \subseteq I$ is a Gröbner basis of $I$ if for every $f \in I$, there exists a $g \in \mathcal{G}$, s. t. $\text{in}_\prec(g) | \text{in}_\prec(f)$. A Gröbner basis $\mathcal{G}$ is called reduced if for two distinct elements $g, g' \in \mathcal{G}$, no term of $g'$ is divisible by $\text{in}_\prec(g)$. The reduced Gröbner basis is unique if we fix an ideal and a term order and require the coefficient of the initial term of every element to be 1.
**Triangulations:** We assume that the reader is familiar with regular and pulling triangulations (see e. g. [5] or [8]). A triangulation is called unimodular if the normalized volume of all simplices contained in it equals 1. Furthermore, we will use the fact that regular triangulations of a point set correspond to a certain class of term orders (see [10, Chapter 8]).

### 3 The Hyperplane Subdivision Method

In this section, we describe a general method for showing degree bounds of generating sets and Gröbner bases of toric ideals that was developed by Haase and Paffenholz ([4], see also [3, Proposition IV.2.5]).

A flow polytope has a canonical subdivision into polytopes contained in lattice translates of a unit cube: we slice $F$ along hyperplanes of type $H_{ak} = \{x | x_a = k\}$. Let $F = F_{G,d,u,l}$ be a flow polytope. For $k \in \mathbb{Z}^A$ we define a cell of $F$ as $Z_F(k) = \{f \in F | k_a \le f_a \le k_a + 1 \text{ for all } a \in A\}$. Cells are flow polytopes using the same graph with tighter upper and lower bounds. Thus, they are lattice polytopes. For our purposes, it is acceptable to identify a cell with the translated cell $Z_F(k) - k \subseteq [0, 1]^A$.

We will use a particular class of regular triangulations that we call *subdivide-and-pull triangulations*. They are obtained in the following way: start by subdividing the flow polytope along hyperplanes into cells as defined above. Then determine a pulling triangulation of each of the cells.

The following theorem is used in our proof of the Main Theorem:

**Theorem 3.1** Let $F$ be a flow polytope and $k \ge 2$. $I_F$ contains a generating set of at most degree $k$ if the toric ideal of every cell of $F$ contains a generating set of at most degree $k$.

Let $\Delta$ be a subdivide-and-pull triangulation of $F$ and $\mathcal{G}$ the reduced Gröbner basis with respect to the term order that corresponds to $\Delta$. $\mathcal{G}$ has at most degree $k$ if all cells have a Gröbner basis of at most degree $k$.

The main ingredient of the proof is the following theorem, which is a conglomerate of Corollaries 8.4 and 8.9 in Sturmfels's book ([10]):

**Theorem 3.2** Let $P$ be a polytope and $\Delta$ be a regular, unimodular triangulation of $P$. Let $\prec_{\Delta}$ be the term order corresponding to $\Delta$. Then, the initial ideal of $I_P$ with respect to $\prec_{\Delta}$ is given by

$$ \mathrm{in}_{\prec_{\Delta}}(I_P) = \langle x^F | F \text{ is a minimal non-face of } \Delta \rangle \quad (4) $$

### 4 On the Proof of the Main Theorem

In this section, we briefly describe the idea of the proof of the Main Theorem. First, the result is proved for transportation polytopes. The general statement can be reduced to this special case.

**Theorem 4.1** *Toric ideals of transportation polytopes are generated in degree 3.*

**Proof (idea):** Due to Theorem 3.1, it suffices to show that the bound holds for all cells. Let $Z$ be a cell of an $(m \times n)$-transportation polytope and let $A = Z \cap \mathbb{Z}^{m \times n}$. Consider the set $J_A$ of binomials in $I_A$ that cannot be expressed by binomials of smaller degree. Let $x^u - x^v \in J_A$ be a binomial s.t. $\min\{d(M, N) | M \in \mathrm{supp}(u), N \in \mathrm{supp}(v)\}$ is minimal over all binomials in $J_A$, where $d$ denotes the Hamming distance. Let $M \in \mathrm{supp}(u)$ and $N \in \mathrm{supp}(v)$ be two matrices realizing this minimal Hamming distance. Suppose $\mathrm{deg}(x^u - x^v) \ge 4$. By an analysis of the matrices $M$ and $N$, we can reach a contradiction. $\square$
**Proof of the Main Theorem:** The Main Theorem can be reduced to Theorem 4.1 by the transformation described in [9, 21.6a]. □

# 5 Gröbner Bases for Transportation Polytopes

In this section, we discuss degree bounds for Gröbner bases of transportation polytopes and we construct Gröbner bases in high degree.

For the toric ideal of the Birkhoff polytope, the following degree bound for their revlex Gröbner bases is known:

**Theorem 5.1 ([2, Theorem 6.1],[10, Theorem 14.8])** Let $I_{B_n}$ be the toric ideal of the Birkhoff polytope $B_n$. Let $\mathcal{G}$ be a reduced Gröbner basis of $I_{B_n}$ with respect to an arbitrary reverse lexicographic term order.

Then, $\mathcal{G}$ has at most degree $n$.

The proof of this theorem can easily be generalized to prove degree bounds for Gröbner bases of transportation polytopes:

**Theorem 5.2** Let $T_{rc}$ be an $(m \times n)$-transportation polytope and let $\prec$ denote a term order that corresponds to a subdivide-and-pull triangulation (as defined in Section 3).

Then, the reduced Gröbner basis of $I_{T_{rc}}$ has at most degree $\lfloor \frac{m \cdot n}{2} \rfloor$.

This improves a known degree bound for reduced Gröbner bases ([10, Proposition 13.15]) by a factor of approximately 2.

Both theorems are (almost) as good as they can get, in the following sense:

**Theorem 5.3 ($B_n$ has revlex Gröbner bases in degree $n$)** Let $n$ be even. Then there exists a revlex term order $\prec$, s. t. the reduced Gröbner basis $\mathcal{G}_{\prec}$ of $I_{B_n}$ has exactly degree $n$.

**Theorem 5.4 (Gröbner bases in high degree for transportation polytopes)** Let $m$ and $n$ be even. Then there exists a smooth $(m \times n)$-transportation polytope $T_{rc}$ and a term order $\prec$, s. t. the reduced Gröbner basis $\mathcal{G}_{\prec}$ of $I_{T_{rc}}$ has degree at least $\frac{m(n-2)}{2}$.

The term order can be chosen to be revlex or it can correspond to a subdivide-and-pull triangulation (as defined in Section 3).

Theorem 5.3 supports the experimental result of Diaconis and Eriksson, who suggested that Gröbner bases of $I_{B_n}$ have exactly degree $n$ ([1, Remark 9]).

We illustrate the constructions used to prove Theorems 5.3 and 5.4 in two examples:

**Example 5.5** This example shows that Theorem 5.3 holds for $n = 6$.

$$ \underbrace{\begin{bmatrix} 1 \\ \mathbf{1} \\ 1 \\ \mathbf{1} \\ 1 \end{bmatrix}}_{A_1} + \underbrace{\begin{bmatrix} 1 \\ \mathbf{1} \\ 1 \\ \mathbf{1} \\ 1 \end{bmatrix}}_{A_2} + \underbrace{\begin{bmatrix} 1 \\ \mathbf{1} \\ 1 \\ \mathbf{1} \\ 1 \end{bmatrix}}_{A_3} + \underbrace{\begin{bmatrix} 1 \\ \mathbf{1} \\ \mathbf{1} \\ \mathbf{1} \\ 1 \end{bmatrix}}_{B_1} + \underbrace{\begin{bmatrix} 1 \\ \mathbf{1} \\ \mathbf{1} \\ \mathbf{1} \\ 1 \end{bmatrix}}_{B_2} + \underbrace{\begin{bmatrix} 1 \\ \mathbf{1} \\ \mathbf{1} \\ \mathbf{1} \\ 1 \end{bmatrix}}_{B_3} \quad (5) $$
$$ = \underbrace{\begin{bmatrix} 1 \\ 1 \\ 1 \\ \hline 1 \\ 1 \\ 1 \end{bmatrix}}_{J_6} + \underbrace{\begin{bmatrix} 1 \\ 1 \\ 1 \\ \hline 1 \\ 1 \\ 1 \end{bmatrix}}_{B} + 2 \cdot \underbrace{\begin{bmatrix} 1 \\ 1 \\ 1 \\ \hline 1 \\ 1 \\ 1 \end{bmatrix}}_{C} + \underbrace{\begin{bmatrix} 1 \\ 1 \\ 1 \\ \hline 1 \\ 1 \\ 1 \end{bmatrix}}_{D_1} + \underbrace{\begin{bmatrix} 1 \\ 1 \\ 1 \\ \hline 1 \\ 1 \\ 1 \end{bmatrix}}_{D_2} = \begin{bmatrix} 1 & 1 & 3 & 1 \\ 1 & 1 & 2 & 1 \\ 1 & 1 & 1 & 3 \\ 3 & 1 & 1 & 1 \\ 1 & 2 & 1 & 1 \\ 1 & 3 & 1 & 1 \end{bmatrix} \quad (6) $$

This equation corresponds to an element of $I_{B_6}$. We order the lattice points in $B_6$ s. t. $J_6$ is minimal and $A_1, A_2, A_3, B_1, B_2, B_3$ are smaller than all the remaining points. In the revlex order $<$ defined by this ordering, the left side of the equation corresponds to the initial term. One can show that it is a minimal generator of the initial ideal in $\prec(I_{B_6})$. Hence, the reduced Gröbner basis of $I_{B_6}$ with respect to $<$ contains an element of degree 6.

**Example 5.6** This example shows that Theorem 5.4 holds for $n = m = 6$. The following equation is a relation of lattice points in the polytope $T_{rc}$ with $r = c = (3, 3, 3, 3, 3, 3)$. A translated version of this relation is contained in the transportation polytope with marginals $r = (39, 39, 39, 39, 39, 39)$ and $c = (3, 3, 3, 3, 3, 219)$. By [4, Lemma 1], this polytope is smooth.

$$ \begin{bmatrix} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \\ \hline 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{bmatrix} + \begin{bmatrix} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \\ \hline 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{bmatrix} + \begin{bmatrix} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \\ \hline 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{bmatrix} + \begin{bmatrix} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \\ \hline 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{bmatrix} + \begin{bmatrix} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \\ \hline 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{bmatrix} + \begin{bmatrix} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \\ \hline 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{bmatrix} \quad (7) $$

$$ + \begin{bmatrix} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \\ \hline 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{bmatrix} + \begin{bmatrix} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \\ \hline 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{bmatrix} + \begin{bmatrix} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \\ \hline 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{bmatrix} + \begin{bmatrix} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \\ \hline 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{bmatrix} + \begin{bmatrix} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \\ \hline 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{bmatrix} \quad (8) $$

$$ = \begin{bmatrix} 2 & 1 & 1 & 10 & 11 & 11 \\ 2 & 1 & 1 & 10 & 11 & 11 \\ 2 & 1 & 1 & 10 & 11 & 11 \\ \hline 10 & 11 & 11 & 2 & 1 & 1 \\ 10 & 11 & 11 & 2 & 1 & 1 \\ 10 & 11 & 11 & 2 & 1 & 1 \end{bmatrix} = 1 \cdot \underbrace{\begin{bmatrix} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \\ \hline 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{bmatrix}}_{C} + 10 \cdot \underbrace{\begin{bmatrix} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \\ \hline 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{bmatrix}}_{D} + \underbrace{\begin{bmatrix} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \\ \hline 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{bmatrix}}_{E} \quad (9) $$

We order the lattice points of $T_{rc}$ s. t. $E$ is minimal and the $A_{ij}$s and $B_{ij}$s are smaller than all the remaining points.
In the revlex order $\prec$ defined by this ordering, the left side of the equation corresponds to the initial term. One can show that it is a minimal generator of the initial ideal in$_{\prec}(I_{T_{rc}})$. Hence, the reduced Gröbner basis of $I_{T_{rc}}$ with respect to $\prec$ contains an element of degree 12.

## Acknowledgements

This article contains the main results of my *Diplomarbeit* (Master's thesis) [7], written in 2007 at Freie Universität Berlin. I would like to thank my advisor Christian Haase for many inspiring hints and discussions.

## References

[1] Persi Diaconis and Nicholas Eriksson. Markov bases for noncommutative Fourier analysis of ranked data. *Journal of Symbolic Computation*, 41(2), February 2006. arXiv:math/0405060v2.

[2] Persi Diaconis and Bernd Sturmfels. Algebraic algorithms for sampling from conditional distributions. *Ann. Statist.*, 26(1):363–397, 1998. Available at http://www-stat.stanford.edu/cgates/PERSI/papers/sturm98.pdf.

[3] Christian Haase. *Lattice Polytopes and Triangulations*. PhD thesis, Technische Universität Berlin, 2000. Available at http://opus.kobv.de/tuberlin/frontdoor.php?source_opus=90.

[4] Christian Haase and Andreas Paffenholz. Quadratic Gröbner bases for smooth 3 × 3 transportation polytopes. *Journal of Algebraic Combinatorics*, 30(4):477–489, 2009. arXiv:math.CO/0607194.

[5] Carl W. Lee. Regular triangulations of convex polytopes. In *Applied Geometry and Discrete Mathematics: The Victor Klee Festschrift*, volume 4 of *DIMACS Series in Discrete Math. and Theor. Comput. Sci.*, pages 443–456. American Mathematical Society, Providence, 1991.

[6] Matthias Lenz. Toric ideals of flow polytopes. arXiv:0801.0495.

[7] Matthias Lenz. Torische Ideale von Flusspolytopen. Master's thesis, Freie Universität Berlin, July 2007. arXiv:0709.3570v3.

[8] Jörg Rambau, Francisco Santos, and Jesus A. De Loera. *Triangulations: Structures for Algorithms and Applications*, volume 25 of *Algorithms and Computation in Mathematics*. Springer, 2010. Not yet published. Available: October 2010.

[9] Alexander Schrijver. *Combinatorial Optimization – Polyhedra and Efficiency*. Number 24A in Algorithms and Combinatorics. Springer, Berlin, 2003.

[10] Bernd Sturmfels. *Gröbner Bases and Convex Polytopes*, volume 8 of *University Lecture Series*. American Mathematical Society, Providence, Rhode Island, 1996.
[11] Bernd Sturmfels. Equations defining toric varieties. Kollár, János (ed.) et al., Algebraic geometry. Proceedings of the Summer Research Institute, Santa Cruz, CA, USA, July 9–29, 1995. Providence, RI: American Mathematical Society. Proc. Symp. Pure Math. 62(pt.2), 437-449, 1997. arXiv: alg-geom/9610018v1.

[12] Günter M. Ziegler. *Lectures on Polytopes*, volume 152 of *GTM*. Springer-Verlag, New York, 1995.