# A subdivision algebra for a product of two simplices via flow polytopes

Matias von Bell  Department of Mathematics
University of Kentucky
<EMAIL_ADDRESS>
###### Abstract.

For any lattice path $\nu$ from the origin to a point $(a,b)$, we construct an
associated flow polytope $\mathcal{F}_{\widetilde{G}_{B}(\nu)}$ arising from
an acyclic graph where bidirectional edges are permitted. We show that the
flow polytope $\mathcal{F}_{\widetilde{G}_{B}(\nu)}$ admits a subdivision
whose dual is a $w$-simplex, where $w$ is the number of valleys in the path
$E\nu N$. Refinements of this subdivision can be obtained by reductions of a
polynomial $P_{\nu}$ in a generalization of Mészáros’ subdivision algebra for
acyclic root polytopes that allows negative roots. Via an integral equivalence
between $\mathcal{F}_{\widetilde{G}_{B}(\nu)}$ and the product of simplices
$\Delta_{a}\times\Delta_{b}$, we obtain a subdivision algebra for a product of
two simplices. As a special case, we give a reduction order for reducing
$P_{\nu}$ which encodes the cyclic $\nu$-Tamari complex of Ceballos, Padrol,
and Sarmiento.

##  1\. Introduction

Given a standard $a$-simplex $\Delta_{a}$ and a standard $b$-simplex
$\Delta_{b}$, their cartesian product is the $(a+b)$-dimensional polytope

$\Delta_{a}\times\Delta_{b}=\mathrm{conv}\\{(\mathbf{e}_{i},\mathbf{e}_{j})\mid\mathbf{e}_{i}\in\Delta_{a}\text{
and }\mathbf{e}_{j}\in\Delta_{b}\\}.$

The triangulations of $\Delta_{a}\times\Delta_{b}$ have been extensively
studied. They serve as building blocks in the study of triangulations of more
complicated polytopes [17, 27], and play an important role in understanding
triangulations more generally [11, 28]. They have also garnered interest from
a variety of perspectives, having connections to algebraic geometry (Schubert
calculus [1], Segre varieties [9], Gröbner bases [29]), tropical geometry
(tropical convexity [14], tropical hyperplane arrangements and oriented
matroids [2, 7], and optimization (dual transportation polytopes [13]).

In this article, we study $\Delta_{a}\times\Delta_{b}$ from the perspective of
flow polytopes, which are a rich family of polytopes with close connections to
many areas including representation theory [3], diagonal harmonics [24],
Schubert polynomials [26], and toric geometry [18]. Flow polytopes arise from
placing flows through directed graphs, and are traditionally defined as
follows. Let $G$ be a connected directed graph with vertex set
$V(G)=\\{1,2,\ldots,n\\}$ and edge multiset $E(G)$ with $m$ edges directed
toward their larger vertex. At each vertex $i\in V(G)$ we assign a netflow
$a_{i}\in\mathbb{Z}$ satisfying the balance condition $\sum_{i=1}^{n}a_{i}=0$,
and hence $a_{n}=-\sum_{i=1}^{n-1}a_{i}$. For
$\mathbf{a}=(a_{1},\ldots,a_{n-1},-\hbox{$\sum_{i=1}^{n}a_{i}$})\in\mathbb{Z}^{n}$,
an $\mathbf{a}$-flow on $G$ is a tuple $(x_{e})_{e\in E}\in\mathbb{R}^{m}$
satisfying

(1) $\sum_{e\in\mathrm{In}(j)}x_{e}-\sum_{e\in\mathrm{Out}(j)}x_{e}=a_{j}$

where $\mathrm{In}(j)$ and $\mathrm{Out}(j)$ respectively denote the set of
incoming and outgoing edges at $j$.

The flow polytope $\mathcal{F}_{G}(\mathbf{a})$ is the set of all
$\mathbf{a}$-flows on $G$. When $\mathbf{a}=\mathbf{e}_{1}-\mathbf{e}_{n}$ we
write $\mathcal{F}_{G}:=\mathcal{F}_{G}(\mathbf{a})$ for brevity. The product
of simplices $\Delta_{a}\times\Delta_{b}$ is now the flow polytope over the
graph $G_{a,b}$ with vertex set $[3]$ and $a+1$ copies of the edge $(1,2)$ and
$b+1$ copies of the edge $(2,3)$. For example, the flow polytope over the
graph on the left in Figure 1 is $\Delta_{4}\times\Delta_{3}$.

$s$$1$$2$$3$$4$$5$$t$$1$$2$$3$$G_{4,3}$$G$ Figure 1. The flow polytopes of the
above graphs are integrally equivalent. In particular
$\mathcal{F}_{G}\equiv\mathcal{F}_{G_{4,3}}=\Delta_{4}\times\Delta_{3}$.

At first glance, the flow polytope perspective does not seem to yield anything
new in regards to triangulations of $\Delta_{a}\times\Delta_{b}$. For example,
any Danilov–Karzanov–Koshevoy triangulation or Stanley–Postnikov triangulation
(see [10, 25]) of $\mathcal{F}_{G_{a,b}}$ only gives a staircase triangulation
of $\Delta_{a}\times\Delta_{b}$. To obtain more triangulations, we slightly
expand the definition of a flow polytope in Section 2 by allowing negative
flows and letting the underlying graph $G$ have bidirectional edges. This lets
us generates a large class of polytopes in Section 3 which are integrally
equivalent to $\Delta_{a}\times\Delta_{b}$. Two lattice polytopes
$\mathcal{P}\subseteq\mathbb{R}^{k}$ and
$\mathcal{Q}\subseteq\mathbb{R}^{\ell}$ are integrally equivalent if there
exists an affine transformation
$\varphi:\mathbb{R}^{k}\rightarrow\mathbb{R}^{\ell}$ whose restriction to
$\mathcal{P}$ is a bijection $\varphi:\mathcal{P}\to\mathcal{Q}$ that
preserves the lattice, meaning $\varphi$ is a bijection between
$\mathbb{Z}^{k}\cap\mathrm{aff}(P)$ and
$\mathbb{Z}^{\ell}\cap\mathrm{aff}(Q)$. If $\mathcal{P}$ and $\mathcal{Q}$ are
integrally equivalent, they have the same face poset, normalized volume and
Ehrhart polynomial, and we write $\mathcal{P}\equiv\mathcal{Q}$. In Section 3
we construct a graph $\widetilde{G}_{B}(\nu)$ determined by a lattice path
$\nu$ from the origin to a point $(a,b)$ in the first quadrant using steps
$N=(0,1)$ and $E=(1,0)$. We then show that
$\mathcal{F}_{\widetilde{G}_{B}(\nu)}\equiv\Delta_{a}\times\Delta_{b}$, and
therefore triangulations of $\mathcal{F}_{\widetilde{G}_{B}(\nu)}$ give
triangulation of $\Delta_{a}\times\Delta_{b}$. The triangulations obtained
hinge on the following decomposition.

######  Theorem 1.1.

The flow polytope $\mathcal{F}_{\widetilde{G}_{B}(\nu)}$ can be written as

$\mathcal{F}_{\widetilde{G}_{B}(\nu)}=\bigcup_{i=1}^{w}\mathcal{Q}_{i}$

where the polytopes $\mathcal{Q}_{1},\mathcal{Q}_{2}$,…, $\mathcal{Q}_{w}$
have pairwise disjoint interiors, and $w$ is the number of valleys in
$\overline{\nu}=E\nu N$. Furthermore, for any nonempty $S\subseteq[w]$ we have
that $\cap_{i\in S}\mathcal{Q}_{i}\equiv\mathcal{F}_{\cap_{i\in
S}\widetilde{G}(\nu,i)}$.

The dual of the subdivision obtained in Theorem 1.1 is a $w$-simplex, and we
refer to it as the simplex-subdivision of
$\mathcal{F}_{\widetilde{G}_{B}(\nu)}$. Theorem 1.1 is reminiscent of a result
by Cho [8, Theorem 16] for the full type $A_{n}$ root polytope. Specifically,
when $a=b$ and $\nu=(NE)^{n}$, the subdivision of $\Delta_{a}\times\Delta_{a}$
induced by Theorem 1.1 projects onto Cho’s subdivision of the full type
$A_{n}$ root polytope.

A useful tool for subdividing certain flow polytopes is Mészáros’ subdivision
algebra [22]. We will describe it in more detail in Section 4, and simply note
here that it is an associative algebra in which dissections of certain flow
polytopes can be encoded algebraically by reductions of monomials. It was
first used to study subdivisions of acyclic root polytopes [22], and has since
also been extensively used to study subdivisions of flow polytopes [19, 20,
26]. In [4], the present author and Yip showed that the subdivision algebra
can be used to subdivide a certain subpolytope $\mathcal{U}_{I,J}$ of a
product of simplices, answering a question of Ceballos, Padrol, and Sarmiento.
In Section 4 we will build off of this result to extend the subdivision
algebra to encode refinements of the simplex-subdivision, thereby obtaining a
large class of triangulations of $\Delta_{a}\times\Delta_{b}$. Letting $M(G)$
denote the monomial corresponding to $G$ in the subdivision algebra, we have
the following.

######  Theorem 1.2.

The simplex-subdivision of $\mathcal{F}_{\widetilde{G}_{B}(\nu)}$ is encoded
in the polynomial

$P_{\nu}=\sum_{\begin{subarray}{c}S\subseteq[w]\\\
S\neq\emptyset\end{subarray}}\beta^{|S|-1}M(\cap_{i\in S}G(\nu,i))$

where $w$ is the number of valleys in $\nu$. Furthermore, reducing $P_{\nu}$
in the subdivision algebra encodes subdivisions of
$\mathcal{F}_{\widetilde{G}_{B}(\nu)}$.

Since all triangulations of a product of simplices are unimodular [12,
Proposition 6.2.11], the triangulations obtained via Theorem 1.2 are
unimodular. Triangulating each $\mathcal{Q}_{i}$ with the subdivision algebra
gives regular triangulations [19, Theorem 3]. It would be interesting to know
if the triangulations obtained by reducing $P_{\nu}$ are also regular.

The volume of each polytope $\mathcal{Q}_{i}$ in Theorem 1.1 is given by the
number of lattice paths weakly above a path $\nu(i)$ obtained by cyclically
shifting $\overline{\nu}$. Obtaining a triangulation for a product of
simplices by cyclically shifting a path was first considered by Ceballos,
Padrol, and Sarmiento in [6], where they introduce the Dyck path triangulation
of $\Delta_{a}\times\Delta_{a}$ and the generalized Dyck path triangulation of
$\Delta_{ka}\times\Delta_{a}$. In [7] they generalize it further to the
$\nu$-cyclohedral triangulation of $\Delta_{a}\times\Delta_{b}$. In Section 5,
we show how to obtain these triangulations using the subdivision algebra by
reducing $P_{\nu}$ with a particular reduction order.

######  Theorem 1.3.

The triangulation of $\mathcal{F}_{\widetilde{G}_{B}(\nu)}$ induced by
reducing $P_{\nu}$ in the reduction order $\rho_{\text{len}}$ is a geometric
realization of the cyclic $\nu$-Tamari complex.

The structure of the article is as follows.

### Structure of the article

In Section 2 we introduce a generalization to the notion of a flow polytope,
by allowing negative flows and bidirectional edges. After checking
polytopality, we show that any such flow polytope is integrally equivalent to
one using the standard definition 2.2. Having shown, in some sense, that our
definition of a flow polytope is uninteresting, we proceed by giving a
counterexample. We begin Section 3 by constructing the flow polytope of
interest in this article, namely $\mathcal{F}_{\widetilde{G}_{B}(\nu)}$, and
then show that it is integrally equivalent to a product of two simplices
(Lemma 3.4). In 3.2 we prove Theorem 1.1, obtaining the simplex-subdivision of
$\mathcal{F}_{G_{B}(\nu)}$. In Section 4 we introduce a subdivision algebra,
and show that the subdivision obtained in Theorem 1.1 can be encoded with a
polynomial $P_{\nu}$ in the subdivision algebra Theorem 1.2. In Section 5 we
introduce the cyclic $\nu$-Tamari complex, and prove Theorem 1.3.

##  2\. Flow polytopes and negative flows

The traditional definition of a flow polytope given in the introduction does
not allow negative flows or bidirectional edges. In this section, we remedy
the situation by giving a slightly modified definition. We will see that flow
polytopes with the modified definition are integrally equivalent to
traditional flow polytopes, which might suggest that the new definition given
is unnecessary. However, the extended definition proves to be pivotal for our
purposes in the remainder of the article.

Let $G$ be a connected directed acyclic graph with vertex set
$V(G)=\\{1,2,\ldots,n\\}$ and edge multiset $E(G)$ with $m$ directed edges. An
edge $(i,j)$ with $i<j$ can be of three possible types: a forward edge
$(i,j,+)$ directed toward $j$, a backward edge $(i,j,-)$ directed toward $i$,
or a bidirectional edge $(i,j,\pm)$. For a vertex $j$, we divide the edges
incident to $j$ into smaller and larger edges, that is, sets $S(j)$ and
$L(j)$, where $S(j)$ denotes the set of edges $(i,j)$ with $i<j$, and let
$L(j)$ denote the set of edges $(j,k)$ with $j<k$. At each vertex $i\in V(G)$
we assign a netflow $a_{i}\in\mathbb{Z}$ satisfying the balance condition
$\sum_{i=1}^{n}a_{i}=0$, and hence $a_{n}=-\sum_{i=1}^{n-1}a_{i}$. For
$\mathbf{a}=(a_{0},\ldots,a_{n},-\hbox{$\sum_{i=1}^{n-1}a_{i}$})\in\mathbb{Z}^{n}$,
an $\mathbf{a}$-flow on $G$ is a tuple $(x_{e})_{e\in E}\in\mathbb{R}^{m}$
satisfying

(2) $\sum_{e\in L(j)}x_{e}-\sum_{e\in S(j)}x_{e}=a_{j}$

with $x_{e}\geq 0$ if $e$ is a forward edge, $x_{e}\leq 0$ if $e$ is a
backward edge, and $x_{e}\in\mathbb{R}$ if $e$ is bidirectional. We think of
$x_{e}$ as the amount of flow in the edge $e$. If a bidirectional edge has
positive flow, we treat it as a forward edge, and if it has negative flow, we
treat it as a backward edge.

The set of all $\mathbf{a}$-flows on $G$ is denoted by
$\mathcal{F}_{G}(\mathbf{a})$. However, as we will consider only the case
$\mathcal{F}_{G}(\mathbf{u})$ with $\mathbf{u}=\mathbf{e}_{1}-\mathbf{e}_{n}$,
we suppress the notation to $\mathcal{F}_{G}:=\mathcal{F}_{G}(\mathbf{u})$. We
prove in Proposition 2.1 that $\mathcal{F}_{G}$ is a convex polytope, which
justfies calling $\mathcal{F}_{G}$ the flow polytope of $G$. When all edges in
$G$ are forward edges, $G$ is necessarily acyclic, and in this case our
definition of a flow polytope agrees with other definitions in the literature,
for example [25] and [21].

The only vertices with non-zero netflow in a $\mathbf{u}$-flow are the
vertices $1$ and $n$, which we call the source and sink respectively. The
vertices $[2,n]$ will be referred to as inner vertices. A route $R$ in $G$ is
a maximal directed path from the source to the sink. Note that an edge in $G$
which is not in a route cannot have non-zero flow, so we can assume that all
edges in $G$ are in some route. Furthermore, since $G$ is acyclic, the source
and sink vertex are each incident to at most one edge in a route. We can
therefore assume that all edges incident to the source and sink are forward
edges. Let $\mathcal{R}$ denote the set of all routes in $G$. To each route
$R\in\mathcal{R}$ we associate a signed characteristic vector
$\mathbf{x}_{R}=(x_{e})_{e\in E(G)}$ as follows. If $e=(i,j)\in R$ with $i<j$,
we set $x_{e}=1$ if the path traverses $e$ from $i$ to $j$, and we set
$x_{e}=-1$ if the path traverses $e$ from $j$ to $i$, and if $e\notin R$, we
set $x_{e}=0$. The following proposition now justifies calling
$\mathcal{F}_{G}$ a flow polytope, and gives an alternate description as the
convex hull of routes.

######  Proposition 2.1.

The set of all $\mathbf{u}$-flows $\mathcal{F}_{G}$ is a polytope if and only
if $G$ is acyclic. Furthermore, when $G$ is acyclic, the vertex description of
$\mathcal{F}_{G}$ is given by

$\mathcal{F}_{G}=\mathrm{conv}\\{\mathbf{x}_{R}\mid R\in\mathcal{R}\\}.$

###### Proof.

First, if $G$ is not acyclic, then it has a cycle $C$. Given any unit flow,
one can arbitrarily change the flow in $C$ while preserving the conservation
of flow condition (2). Thus the set of unit flows is not bounded and hence not
a polytope.

If $G$ is acyclic, we show that
$\mathcal{F}_{G}=\mathrm{conv}\\{\mathbf{x}_{R}\mid R\in\mathcal{R}\\}$ and
hence a polytope. We can label the routes in $\mathcal{R}$ such that
$\mathcal{R}=\\{R_{1},\ldots,R_{k}\\}$ for some positive integer $k$, and we
let $\mathbf{x}_{i}$ denote the signed characteristic vector for $R_{i}$.
Letting $\mathbf{p}\in\mathrm{conv}\\{\mathbf{x}_{R}\mid R\in\mathcal{R}\\}$,
we can now write $\mathbf{p}=\sum_{i=1}^{k}\lambda_{i}\mathbf{x}_{i}$ where
$\lambda_{i}\in\mathbb{R}_{\geq 0}$ and $\sum_{i=1}^{k}\lambda_{i}=1$. Note
that the netflow at vertex $1$ is given by the sum $\sum\lambda_{i}$ where the
sum is taken over only the indices of routes using an edge in $L(1)$. However,
since every route in $\mathcal{R}$ must begin with an edge in $L(1)$, the
netflow at vertex $1$ is $\sum_{i=1}^{k}\lambda_{i}=1$. Similarly we obtain
that the netflow at vertex $n$ is $-1$. Furthermore, since each
$\mathbf{x}_{i}$ adds no netflow at any inner vertex we see that any linear
combination $\sum_{i=1}^{k}\lambda_{i}\mathbf{x}_{i}$ also has netflow $0$ at
each inner vertex. Thus $\mathbf{p}\in\mathcal{F}_{G}$.

Let $\mathbf{q}_{1}$ be a $\mathbf{u}$-flow in $\mathcal{F}_{G}$, and let
$q_{1,e}$ denote the coordinate of $\mathbf{q}_{1}$ corresponding to the edge
$e$. We construct $\mathbf{q}_{1}$ as a linear combination of routes in an
iterative fashion. Consider an edge $e_{1}\in R_{1}$ such that $|q_{1,e_{1}}|$
is minimal, and let $\lambda_{1}=|q_{1,e_{1}}|$. Then
$\mathbf{q}_{1}-\lambda_{1}\mathbf{x}_{1}$ is a
$((1-\lambda_{1})\mathbf{u})$-flow. Let
$\mathbf{q}_{2}=\mathbf{q}_{1}-\lambda_{1}\mathbf{x}_{1}$ and consider an edge
$e_{2}\in R_{2}$ such that $|q_{2,e_{2}}|$ is minimal and let
$\lambda_{2}=|q_{2,e_{2}}|$. We obtain that
$\mathbf{q}_{1}-\lambda_{1}\mathbf{x}_{1}-\lambda_{2}\mathbf{x}_{2}$ is a
$((1-\lambda_{1}-\lambda_{2})\mathbf{u})$-flow. We continue this process,
constructing a $((1-\sum_{i=1}^{j}\lambda_{i})\mathbf{u})$-flow
$\mathbf{q}_{j}$ for each $R_{j}\in\mathcal{R}$ by removing the maximal amount
of flow from all edges in $R_{j}$. At each step the netflow of inner vertices
is unaffected, while the netflow at the source decreases by $\lambda_{i}$ and
the netflow at the sink increases by $\lambda_{i}$. This process can be
continued until we obtain that
$\mathbf{q}_{1}-\sum_{i=1}^{k}\lambda_{i}\mathbf{x}_{i}$ is a
$((1-\sum_{i=1}^{k}\lambda_{i})\mathbf{u})$-flow. If there remains an edge $e$
in $G_{B}$ with non-zero flow in the
$((1-\sum_{i=1}^{k}\lambda_{i})\mathbf{u})$-flow, then by conservation of flow
$e$ is either in a cycle or a route. Since $G$ is acyclic, $e$ must be in a
route $R_{j}$ with non-zero flow in the
$((1-\sum_{i=1}^{k}\lambda_{i})\mathbf{u})$-flow on $G$. This contradicts the
fact that the largest possible flow in $R_{j}$ was subtracted at step $j$.
Thus all edges in an $((1-\sum_{i=1}^{k}\lambda_{i})\mathbf{u})$-flow on $G$
are zero. It then follows that
$\mathbf{q}_{1}=\sum_{i=1}^{k}\lambda_{i}\mathbf{x}_{i}$ and
$\sum_{i=1}^{k}\lambda_{i}=1$, and therefore
$\mathcal{F}_{G}=\mathrm{conv}\\{\mathbf{x}_{R}\mid R\in\mathcal{R}\\}$.

It remains to show that every route in $\mathcal{R}$ corresponds to a vertex
of $\mathcal{F}_{G}$. Note that since $\mathcal{F}_{G}$ is a lattice polytope
in $[-1,1]^{m}$ not containing the origin, it cannot have interior lattice
points. It then suffices to show that no three vectors in
$\\{\mathbf{x}_{R}\mid R\in\mathcal{R}\\}$ are colinear. Let
$\mathbf{x}_{u}=\mu_{1}\mathbf{x}_{v}+\mu_{2}\mathbf{x}_{w}$ for routes
$R_{u}$, $R_{v}$, and $R_{w}$, and $\mu_{1}$, $\mu_{2}\in\mathbb{R}$. We show
that the vectors $\mathbf{x}_{u}$, $\mathbf{x}_{v}$ and $\mathbf{x}_{w}$
cannot be distinct. Let $e$ be the edge in $R_{u}$ incident to the source.
Then $x_{u,e}=1$ as source edges are forward edges. Now $x_{v,e}$ and
$x_{w,e}$ cannot both be zero since $\mu_{1}x_{v,e}+\mu_{2}x_{w,e}=1$. If
$x_{v,e}=1$ and $x_{w,e}=0$, then $\mu_{1}=1$. In this case the equation
$\mu_{1}x_{v,f}+\mu_{2}x_{w,f}=x_{u,f}=0$ must also be satisfied, where $f$ is
the edge of $R_{w}$ incident to the source. Since $x_{v,f}=0$, it follows that
$\mu_{2}=0$, and thus $\mathbf{x}_{u}=\mathbf{x}_{v}$. Similarly if
$x_{v,e}=0$ and $x_{w,e}=1$, we obtain that $\mathbf{x}_{u}=\mathbf{x}_{w}$.
If $x_{v,e}=x_{w,e}=1$, then $\mu_{1}+\mu_{2}=1$. Now either $R_{v}=R_{w}$, or
there exists an edge $g$ in $R_{v}$ which is not in $R_{w}$. In the latter
case we obtain that $x_{v,g}=0$ or $x_{w,g}=0$. Then either $\mu_{1}=0$ or
$\mu_{2}=0$, respectively yielding that $\mathbf{x}_{u}=\mathbf{x}_{w}$ or
$\mathbf{x}_{u}=\mathbf{x}_{v}$. ∎

Having now shown that our notion of a flow polytope is well-defined, we can
make explicit its connection to the original definition.

######  Lemma 2.2.

Let $G$ be an acyclic digraph. Then $\mathcal{F}_{G}$ is integrally equivalent
to a flow polytope $\mathcal{F}_{G^{*}}$, where all edges of $G^{*}$ are
forward edges.

###### Proof.

First we consider backward edges in $G$. Since $G$ is acyclic, the vertex
labels can be permuted such that $G$ has no backward edges. Changing the
orientation of a backward edge $e$ amounts to reflecting the flow polytope
about the hyperplane $x_{e}=0$, which is an integral equivalence.

Next we show that the operation of contracting a bidirectional edge
$(i,j,\pm)$ with $i<j$ is an integral equivalence. If the edge $(i,j,\pm)$ is
the $k$-th edge in a fixed ordering of the edges of $G$, the integral
equivalence is given by $\varphi:\mathbb{R}^{m}\to\mathbb{R}^{m-1}$, where

$\varphi(x_{1},\ldots,x_{k},\ldots,x_{m})=(x_{1},\ldots,\widehat{x}_{k},\ldots,x_{m}).$

Let $D$ denote the set of edges incident to $i$ not including $(i,j,\pm)$.
Define a map $\psi:\mathbb{R}^{m-1}\to\mathbb{R}^{m}$ by

$\psi(x_{1},\ldots,\widehat{x}_{k},\ldots,x_{m})=(x_{1},\ldots,x_{k-1},\left(\sum_{e\in
L(i)\cap D}x_{e}-\sum_{e\in S(i)}x_{e}\right),x_{k+1},\ldots,x_{m}).$

Now restricting $\varphi$ to $\mathcal{F}_{G}$ gives a bijection between
$\mathcal{F}_{G}$ and $\mathcal{F}_{G/(i,j,\pm)}$, with its inverse given by
restricing $\psi$ to $\mathcal{F}_{G/(i,j,\pm)}$. It is also easy to verify
that $\varphi$ restricts to a bijection between
$\mathbb{Z}^{m}\cap\mathrm{aff}(\mathcal{F}_{G})$ and
$\mathbb{Z}^{m-1}\cap\mathrm{aff}(G/(i,j,\pm))$. ∎

An edge $(i,j)$ is said to be idle if it is the only outgoing edge from $i$,
or it is the only incoming edge to $j$. In the remainder of the article, we
will make use of the following lemma.

######  Lemma 2.3.

([26, Lemma 2.2], [16, Corollary 2.13]) If $G^{\prime}$ is obtained from $G$
by contracting idle edges, then
$\mathcal{F}_{G^{\prime}}\equiv\mathcal{F}_{G}$.

##  3\. The flow polytope $\mathcal{F}_{\widetilde{G}_{B}(\nu)}$ and its
simplex subdivisions

In this section we introduce the main flow polytope of consideration in this
article. We then show that it has polyhedral subdivisions which are dual to a
simplex. Each of the interior faces in this subdivision is integrally
equivalent to a flow polytope, with one of the full-dimensional faces being
the integrally equivalent to the $\nu$-caracol flow polytope studied in [4].

###  3.1. The flow polytope $\mathcal{F}_{\widetilde{G}_{B}(\nu)}$.

Let $a$ and $b$ be nonnegative integers, and let $\nu$ be a lattice path from
$(0,0)$ to $(a,b)$, with steps $E=(1,0)$ and $N=(0,1)$. Let
$\overline{\nu}:=E\nu N$, and consider it as a word on $a+b+2$ letters in the
alphabet $\\{E,N\\}$. We write
$\overline{\nu}=\prod_{i=1}^{w}E^{a_{i}}N^{b_{i}}$, with $a_{i}>0$ and
$b_{i}>0$ for $1\leq i\leq w$, where $w$ is the number of valleys (consecutive
$EN$ pairs) in $\overline{\nu}$. To distinguish between the $E$ steps and $N$
steps in $\overline{\nu}$, we index them as follows. Reading the letters from
left to right in $\overline{\nu}$, each letter is indexed with the next
positive integer, with the exception that the first $N$ in a run of $N$ steps
receives the index of the preceding $E$ step. We refer to such an indexing as
the canonical indexing of $\overline{\nu}$. For example,
$E_{1}N_{1}E_{2}E_{3}N_{3}N_{4}E_{5}N_{5}$ is the canonical indexing of
$\overline{\nu}=ENEENNEN$. Let $I$ be the set of indices of $E$ steps and let
$J$ be the set of indices of $N$ steps. We have that
$|I|=a+1=\sum_{i=1}^{w}a_{i}$ and $|J|=b+1=\sum_{i=1}^{w}b_{i}$. Furthermore,
the set of valleys of $\overline{\nu}$ are indexed by elements in $V=I\cap J$.

######  Definition 3.1.

For a path $\overline{\nu}$ with its letters indexed by $\\{1,...,n\\}$
according to the canonical indexing, we define the $\nu$-graph denoted
$G(\nu)$ to be the graph on vertex set $[n]$ and edge set defined as follows.
A pair $(i,j)$ is an edge of $G(\nu)$ if and only if $E_{i}\cdots N_{j}$ is a
subword of $\overline{\nu}$ and its only valleys are of the form $E_{k}N_{k}$
with $k=i$ or $k=j$. All edges in $G(\nu)$ are directed forward. The
bidirectional $\nu$-graph $G_{B}(\nu)$ is the graph $G(\nu)$, but with edges
$(i,j)$ being bidirectional whenever $i$ and $j$ are in $I\cap J$.

By construction, the bidirectional edges in $G_{B}(\nu)$ form a path of length
$w-1$. When $\overline{\nu}$ has only one valley, there are no edges whose end
points are in $I\cap J$, in which case $G_{B}(\nu)=G(\nu)$.

######  Definition 3.2.

The augmentation of a digraph $G$ on vertex set $[n]$, denoted $\widehat{G}$,
is the graph obtained by adding to $G$ a source $s$ and sink $t$, along with
the set of forward edges $\\{(s,i),(i,t)\mid i\in[n]\\}$. The partial
augmentation of $G$, denoted $\widetilde{G}$, is obtained from the full
augmentation by removing edges $(s,i)$ where $i$ has out-degree one, and any
edges $(j,t)$ where $j$ has indegree one.

See Figure 2 for an example of a graph $G_{B}(\nu)$ and its partial
augmentation $\widetilde{G}_{B}(\nu)$.

######  Remark 3.3.

A flow polytope integrally equivalent to $\mathcal{F}_{\widetilde{G}(\nu)}$
was first considered in [23], where its volume was shown to be counted by the
number of lattice paths weakly above $\nu$. In [5], it was considered under
the name $\nu$-caracol flow polytope, and shown to have triangulations whose
dual graphs are Hasse diagrams of a $\nu$-Tamari lattice and a principal order
ideal in Young’s lattice. In [4], it was used to obtain a subdivision algebra
for a subpolytope $\mathcal{U}_{I,\overline{J}}$ of
$\Delta_{a}\times\Delta_{b}$ considered in [7].

######  Lemma 3.4.

Let $\nu$ be a lattice path from $(0,0)$ to $(a,b)$. The flow polytope
$\mathcal{F}_{\widetilde{G}_{B}(\nu)}$ is integrally equivalent to the product
of simplices $\Delta_{a}\times\Delta_{b}$.

###### Proof.

By construction, an inner edge of $\widetilde{G}(\nu)$ is either idle or
bidirectional. Thus contracting the idle inner edges and bidirectional edges
yields the graph on vertex set $\\{s,1,t\\}$ with $a+1$ edges of the form
$(s,1)$ and $b+1$ edges of the form $(1,t)$. The flow polytope over this
resulting graph is $\Delta_{a}\times\Delta_{b}$. ∎

$1$$2$$3$$4$$5$$6$$s$$1$$2$$3$$4$$5$$6$$t$$\overline{\nu}=E_{1}N_{1}E_{2}E_{3}N_{3}N_{4}E_{5}E_{6}N_{6}$$G_{B}(\nu)$$\widetilde{G}_{B}(\nu)$
Figure 2. A graph $G_{B}(\nu)$ with its $\nu$-augmented counterpart
$\widetilde{G}_{B}(\nu)$.

###  3.2. The simplex-subdivision.

We can now subdivide $\mathcal{F}_{\widetilde{G}_{B}(\nu)}$ into a union of
$w$ interior disjoint polytopes. Let $v_{i}$ denote the $i$-th valley in
$I\cap J$. In Figure 2 for example, $I\cap J=\\{1,3,6\\}$, so $v_{1}=1$,
$v_{2}=3$ and $v_{3}=6$. For $1\leq i<w$, let $\mathcal{Q}_{i}$ denote the
convex hull of the routes in $\widetilde{G}_{B}(\nu)$ with the bidirectional
edge $(v_{i},v_{i+1},\pm)$ replaced with the backward edge $(v_{i},v_{i+1},-)$
such that if the route contains backward edges, then it contains the edge
$(v_{i},v_{i+1},-)$. Additionally, we let
$\mathcal{Q}_{w}=\widetilde{G}(\nu)$.

Let $C_{\nu}$ denote the cycle graph on $I\cap J$ with edges
$\\{(v_{1},v_{2},+),(v_{2},v_{3},+),\ldots,(v_{w-1},v_{w},+)$,
$(v_{w},v_{1},-)\\}$. Let $C_{\nu}(i)$ denote the graph $C_{\nu}$ without the
edge beginning at $v_{i}$, and let $G(\nu,i)$ denote the graph obtained by
replacing the bidirectional path in $G_{B}(\nu)$ with $C_{\nu}(i)$. Note in
particular that $G(\nu,w)=G(\nu)$ since $C_{\nu}(w)$ is the directed path from
$v_{1}$ to $v_{w}$. See Figure 3 for an example.

$1$$2$$3$$4$$5$$1$$2$$3$$4$$5$$1$$2$$3$$4$$5$$1$$2$$3$$4$$5$$1$$2$$3$$4$$5$$G_{B}(\nu)$$G(\nu,4)=G(\nu)$$G(\nu,1)$$G(\nu,2)$$G(\nu,3)$
Figure 3. Decomposing $G_{B}(\nu)$ into the possible $G(\nu,i)$. The flow
polytope $\mathcal{F}_{\widetilde{G}_{B}(\nu)}$ decomposes into
$\cup_{i\in[w]}\mathcal{Q}_{i}$, where
$\mathcal{Q}_{i}\equiv\mathcal{F}_{\widetilde{G}(\nu,i)}$ for each $i\in[w]$.

See 1.1

###### Proof.

We begin by checking that
$\mathcal{F}_{\widetilde{G}_{B}(\nu)}=\bigcup_{i=1}^{w}\mathcal{Q}_{i}$. Let
$\mathbf{x}_{1}\in\mathcal{F}_{\widetilde{G}_{B}(\nu)}$, we show that it can
be written as a convex combination of routes in some $\mathcal{Q}_{i}$. Let
$I_{1}$ denote the indices of the entries in $\mathbf{x}_{1}$ with negative
flow, i.e. $I_{1}=\\{k\mid x_{1,e_{k}}<0\\}$ If $I_{1}=\emptyset$, then
$\mathbf{x}_{1}\in\mathcal{F}_{\widetilde{G}(\nu)}=\mathcal{Q}_{w}$. If
$I_{1}\neq\emptyset$, we choose edges $e_{j_{1}}=(v_{h_{1}},v_{h_{1}+1},-)$
and $e_{k_{1}}=(v_{\ell_{1}-1},v_{\ell_{1}},-)$ from $\\{e_{k}\mid k\in
I_{1}\\}$ (not necessarily distinct) such that $v_{h_{1}}$ is minimal and
$v_{\ell_{1}}$ is maximal. Let $R_{1}$ be the route with edges
$\\{(s,v_{\ell_{1}},+)$, $(v_{\ell_{1}-1},v_{\ell_{1}},-)$, $\ldots$,
$(v_{h_{1}},v_{h_{1}+1},-)$, $(v_{h_{1}},t,+)\\}$, which exists since the
bidirectional edges form a path. Now $R_{1}$ is the shortest route containing
all edges with negative flow. By conservation of flow, the edges
$(s,v_{\ell_{1}},+)$ and $(v_{h_{1}},t,+)$ must have positive flow.
Furthermore, the flow in $(v_{h_{1}},t,+)$ must be greater than or equal to
$|x_{e_{k_{1}}}|$, and the flow in $(s,v_{\ell_{1}},+)$ must be greater than
or equal to $|x_{e_{j_{1}}}|$. Letting $\alpha_{1}=|x_{e_{k_{1}}}|$, we have
that $\mathbf{x}_{2}=\mathbf{x}_{1}-\alpha_{1}\mathbf{x}_{R_{1}}$ is a
$(1-\alpha_{1})\mathbf{u}$-flow on $\widetilde{G}_{B}(\nu)$ in which the edge
$e_{k_{1}}$ has zero flow, and the flow in the edges $(s,v_{\ell_{1}},+)$ and
$(v_{h_{1}},t,+)$ is non-negative. Letting $I_{2}=\\{k\mid x_{2,e_{k}}<0\\}$,
we now have $I_{2}\subsetneq I_{1}$. If $I_{2}\neq\emptyset$, we continue as
before, choosing edges $e_{j_{2}}=(v_{h_{2}},v_{h_{2}+1},-)$ and
$e_{k_{2}}=(v_{\ell_{2}-1},v_{\ell_{2}},-)$ from $\\{e_{k}\mid
x_{2,e_{k}}<0\\}$ with minimal $v_{h_{2}}$ and maximal $v_{\ell_{2}}$. Taking
$R_{2}$ to be the route with edges $\\{(s,v_{\ell_{2}},+)$,
$(v_{\ell_{2}-1},v_{\ell_{2}},-)$, $\ldots$, $(v_{h_{2}},v_{h_{2}+1},-)$,
$(v_{h_{2}},t,+)\\}$, we obtain the shortest route containing all edges with
negative flow. Letting $\alpha_{2}=|x_{e_{k_{2}}}|$, we have that
$\mathbf{x}_{3}:=\mathbf{x}_{2}-\alpha_{2}\mathbf{x}_{R_{2}}$ is a
$(1-\alpha_{1}-\alpha_{2})\mathbf{u}$-flow on $\widetilde{G}_{B}(\nu)$ in
which the edge $e_{k_{2}}$ has zero flow, and the flow in the edges
$(s,v_{\ell_{2}},+)$ and $(v_{h_{2}},t,+)$ is non-negative. We proceed in this
fashion until we obtain a $(1-\sum_{k=1}^{r}\alpha_{k})\mathbf{u}$-flow
$\mathbf{x}_{r+1}$ with no negative entries, so $\emptyset=I_{r+1}\subsetneq
I_{r}\subsetneq\cdots\subsetneq I_{1}$. Let $i$ be the index in $I_{r-1}$ of
the edge $(v_{\ell_{r}-1},v_{\ell_{r}},-)$. Necessarily, $e_{i}$ is an edge
with minimal flow in $\mathbf{x}_{1}$, and by construction the routes
$R_{1},...,R_{r}$ all share the edge $e_{i}$. As $\mathbf{x}_{r+1}$ has no
negative entries, we can write it as a convex combination of a set our routes
$R_{r},\ldots,R_{u}$ in $\widetilde{G}(\nu)\setminus e_{i}$. In particular,
$\mathbf{x}_{r+1}=\sum_{k=r}^{u}\alpha_{k}\mathbf{x}_{R_{k}}$ such that
$\alpha_{k}\geq 0$ for all $r\leq k\leq u$ and
$\sum_{k=r}^{u}\alpha_{k}=(1-\sum_{k=1}^{r}\alpha_{k})$. We can thus write
$\mathbf{x}_{1}$ as the convex combination
$\mathbf{x}_{1}=\sum_{k=1}^{u}\alpha_{k}\mathbf{x}_{R_{k}}$, with
$\alpha_{k}\geq 0$ for all $k$ and $\sum_{k=1}^{u}\alpha_{k}=1$. Since all
routes $R_{1},...,R_{u}$ are vertices in $\mathcal{Q}_{i}$, we have that
$\mathbf{x}\in\mathcal{Q}_{i}$. It follows that
$\mathcal{F}_{\widetilde{G}_{B}(\nu)}\subseteq\cup_{i=1}^{w}\mathcal{Q}_{i}$,
and the reverse inclusion is immediate.

To see that $\mathcal{Q}_{i}$ and $\mathcal{Q}_{j}$ have disjoint interiors
for any $i,j\in[w]$ with $i\neq j$ we observe that $\mathcal{Q}_{i}$ and
$\mathcal{Q}_{j}$ lie in the positive and negative half-spaces of the
hyperplane determined by $x_{(v_{i},v_{i+1})}=x_{(v_{j},v_{j+1})}$. If $i=w$
and $j\neq w$, then $\mathcal{Q}_{i}$ and $\mathcal{Q}_{j}$ are cut by the
hyperplane $x_{(v_{j},v_{j+1})}=0$.

It remains to show that for $S\subseteq[w]$ we have $\cap_{i\in
S}\mathcal{Q}_{i}\equiv\mathcal{F}_{\cap_{i\in S}\widetilde{G}(\nu,i)}$. As
noted earlier, $\widetilde{G}(\nu,w)=\widetilde{G}(\nu)$, and so if $w\in S$,
then $\cap_{i\in S}\mathcal{Q}_{i}=\mathcal{F}_{\cap_{i\in
S}\widetilde{G}(\nu,i)}$. In the case that $w\notin S$, we construct an
integral equivalence $\varphi$ as follows. First fix and ordering
$e_{1},\ldots,e_{m+1}$ on the set of edges in
$\widetilde{G}_{B}(\nu)\cup(v_{1},v_{w})$ (as undirected edges) so that
$e_{i}=(v_{i},v_{i+1})$ for each $i\in[w-1]$ and $e_{w}=(v_{1},v_{w})$. Then
$\cap_{i\in S}\mathcal{Q}_{i}$ and $\mathcal{F}_{\cap_{i\in
S}\widetilde{G}(\nu,i)}$ both embed into $\mathbb{R}^{m+1}$, and we define
$\varphi:\mathbb{R}^{m+1}\to\mathbb{R}^{m+1}$ to be the linear transformation

$\mathbf{x}\mapsto\mathbf{x}+x_{\min(S)}\mathbf{e}_{w}-x_{\min(S)}\sum_{i=1}^{w-1}\mathbf{e}_{i}.$

By construction, a route $R$ in $\cap_{i\in S}\mathcal{Q}_{i}$ must contain
all or none of the edges $(v_{i},v_{i+1},-)$ with $i\in S$. Thus for a vertex
$\mathbf{x}_{R}$, either $x_{i}=0$ for all $i\in S$ or $x_{i}=-1$ for all
$i\in S$. In both cases, $R$ is uniquely determined by its edges $e_{s}$ and
$e_{t}$ incident to the source and sink respectively. Now $\varphi$ maps
$\mathbf{x}_{R}$ to the unique route in $\cap_{i\in S}\widetilde{G}(\nu,i)$
determined by $e_{s}$ and $e_{t}$. It follows that $\varphi$ restricts to a
bijection between $\mathrm{aff}(\cap_{i\in S}\mathcal{Q}_{i})$ and
$\mathrm{aff}(\cap_{i\in S}\widetilde{G}(\nu,i))$, with inverse $\varphi^{-1}$
given by
$\varphi(\mathbf{x})=\mathbf{x}-x_{w}\mathbf{e}_{w}+x_{w}\sum_{i=1}^{w-1}\mathbf{e}_{i}$.
This restriction of $\varphi$ is a bijection between $\cap_{i\in
S}\mathcal{Q}_{i}$ and $\cap_{i\in S}\widetilde{G}(\nu,i)$, while mapping
lattice points to lattice points.

∎

For any non-empty $k$-subset $S$ of $[w]$, $\cap_{i\in S}\widetilde{G}(\nu,i)$
has $k-1$ less edges than $\widetilde{G}(\nu,i)$. In particular,
$\mathcal{F}_{\cap_{i\in S}\widetilde{G}(\nu,i)}$ is a codimension $k-1$ inner
face of the subdivision. Since this holds for all non-empty $k$-subsets of
$[w]$ where $1\leq k\leq w$, we have the following corollary.

######  Corollary 3.5.

The dual to the subdivision $\cup_{i=1}^{w}\mathcal{Q}_{i}$ of
$\mathcal{F}_{\widetilde{G}_{B}(\nu)}$ is a $w$-simplex.

For this reason, we refer to the subdivision of Theorem 1.1 as the simplex-
subdivision of $\mathcal{F}_{\widetilde{G}_{B}(\nu)}$. We refer to the
subdivision of $\Delta_{a}\times\Delta_{b}$ via the integral equivalence in
Lemma 3.4 as the simplex-subdivision induced by $\nu$.

######  Remark 3.6.

In the special case that $\nu=(NE)^{n}$, projecting the simplex-subdivision of
$\Delta_{n}\times\Delta_{n}$ induced by $\nu$ along the span of the vectors
$\\{(\mathbf{e}_{i},\mathbf{e}_{i})\mid i\in[n]\\}$ gives Cho’s subdivision of
the full root polytope of type $A_{n}$ in [8] (also called the Legendre
polytope in [15]).

##  4\. The subdivision algebra

The subdivision algebra is an associative algebra given by Mészáros in which
subdivisions of acyclic root polytopes [22] and certain flow polytopes [19]
can be interpreted as reductions of monomials. In this section we use the
simplex-subdivision from Theorem 1.1 to extend this tool of obtaining
triangulations to a product of two simplices.

We begin with a quick overview of the subdivision algebra for flow polytopes.
Let $G$ be a digraph with all forward edges, and let $(i,j)$ and $(j,k)$ be a
pair of edges in $G$ satisfying $i<j<k$ (we omit signs as all edges are
forward edges). Let

$\displaystyle G_{1}$ $\displaystyle:=(G\setminus\\{(i,j)\\})\cup\\{(i,k)\\},$
$\displaystyle G_{2}$
$\displaystyle:=(G\setminus\\{(j,k)\\})\cup\\{(i,k)\\},\text{ and}$
$\displaystyle G_{3}$
$\displaystyle:=(G\setminus\\{(i,j),(j,k)\\})\cup\\{(i,k)\\}.$

######  Lemma 4.1.

(Reduction lemma [19, Lemma 2.2], [26, Proposition 2.3] ) Let $G$ be a digraph
with $G_{1}$, $G_{2}$, and $G_{3}$ obtained from $G$ as above. Then there
exists interior disjoint polytopes $\mathcal{P}_{1}$ and $\mathcal{P}_{2}$
such that $\mathcal{F}_{\widehat{G}}=\mathcal{P}_{1}\cup\mathcal{P}_{2}$,
where $\mathcal{P}_{1}\equiv\mathcal{F}_{\widehat{G}_{1}}$,
$\mathcal{P}_{2}\equiv\mathcal{F}_{\widehat{G}_{2}}$, and
$\mathcal{P}_{1}\cap\mathcal{P}_{2}\equiv\mathcal{F}_{\widehat{G}_{3}}.$

Such a subdivision is called a reduction. A reduction of $G$ can be viewed as
rooted tree, with $G$ as the root with the graphs $G_{1}$, $G_{2}$, and
$G_{3}$ as leaves. Continuing to perform reductions on the leaves until no
more reductions are possible, we obtain a rooted ternary tree called a
reduction tree. It is important to note here that when a reduction is
performed on a leaf at a pair $(i,j),(j,k)$, the same pair is reduced in all
other leaves where such a reduction is possible. A reduction tree obtained in
this way is not unique in general, and depends on the reduction order.
However, the number of leaves in two reduction trees of a graph is always the
same and the following holds.

######  Lemma 4.2.

([19, Lemma 1]) For two reduction trees of a graph $G$, let $r_{k}^{1}$ and
$r_{k}^{2}$ denote the number leaves in the two reduction trees with $k$
edges. Then $r_{k}^{1}=r_{k}^{2}$.

######  Proposition 4.3.

([19, Theorem 3]) The leaves of a reduction tree encode a regular flag
triangulation of $\mathcal{F}_{\widehat{G}}$. Each leaf with $|E(G)|-k$ edges
encodes a codimension $k$ inner face of the triangulation.

We note here that the reduction lemma also holds for partially augmented
graphs, as the removed edges are only in routes of $\widehat{G}$ which
correspond to cone points of a triangulation obtained in this way, that is,
they are contained in all facets of the triangulation.

A reduction can be encoded algebraically with the relation

$x_{ij}x_{jk}=x_{ij}x_{ik}+x_{ik}x_{jk}+\beta x_{ik}.$

Figure 4 gives a visualization of a reduction. Sometimes it is more convenient
to consider simple reductions, which only encode the full-dimensional
polytopes in a subdivision. These are obtained by using the above reduction
relation and setting $\beta=0$.

$i$$j$$k$$i$$j$$k$$i$$j$$k$$i$$j$$k$$x_{ij}x_{jk}$$x_{ij}x_{ik}$$x_{ik}x_{jk}$$\beta
x_{ik}$ Figure 4. The graphical representation of a reduction, and the
associated terms in the subdivision algebra.

######  Definition 4.4.

The subdivision algebra $\mathcal{S}(\beta)$ is an associative and commutative
algebra over the ring of polynomials $\mathbb{Z}[\beta]$, generated by the
elements $\\{x_{ij}\mid i\neq j\\}$, subject to the relation
$x_{ij}x_{jk}=x_{ik}x_{ij}+x_{jk}x_{ik}+\beta x_{ik}$, where $i\neq k$. For
fixed $i$,$j$, and $k$, replacing all terms $x_{ij}x_{jk}$ in a polynomial $P$
in $\mathcal{S}(\beta)$ with $x_{ik}x_{ij}+x_{jk}x_{ik}+\beta x_{ik}$ is
called a reduction. If applying a sequence of reductions to $P$ yields a
polynomial $R$ which cannot be reduced further, we say that $R$ is a reduced
form of $P$.

This definition is slightly more general than the usual definition given by
Mészáros in that here a generator $x_{ij}$ need not satisfy $i<j$, and we do
not require that $i<j<k$ in a reduction. A non-commutative version was also
studied by Mészáros in [22]. Let us consider a small example.

######  Example 4.5.

Let $P=x_{12}x_{24}x_{52}+x_{12}x_{24}\beta$. We can apply reductions as
follows.

$\displaystyle\mathbf{x_{12}x_{24}}x_{52}$
$\displaystyle=x_{12}x_{14}x_{52}+x_{14}\mathbf{x_{24}x_{52}}+x_{14}x_{52}\beta$
$\displaystyle=x_{12}x_{14}x_{52}+x_{14}x_{52}x_{54}+x_{14}x_{24}x_{54}+x_{14}x_{54}\beta+x_{14}x_{52}\beta$

The pairs in bold indicate the reductions. Since no more reductions are
possible, the resulting polynomial is a reduced form of $P$.

Given a digraph $G$ with forward and backward edges, we associate a forward
edge $(i,j,+)$ and a backward edge $(i,j,-)$ with the generators $x_{ij}$ and
$x_{ji}$ in $\mathcal{S}(\beta)$ respectively. The graph $G$ can then be
encoded with the monomial $M(G):=\prod_{(i,j,+)\in
E(G)}x_{ij}\prod_{(i,j,-)\in E(G)}x_{ji}$.

Define a cyclic peak of a lattice path to be a consecutive $NE$ pair in a
cyclic reading of the steps in the path. In particular, the only cyclic peak
which is not a peak occurs when the path begins with $E$ and ends with $N$.
Given a path $\nu$, we define $\overline{\nu}(k)$ to be the path obtained by
reading the steps of $\overline{\nu}$ beginning at the $E$ step of the $k$-th
cyclic peak. We begin counting from the first cyclic peak which is also a peak
of $\overline{\nu}$. Since $\overline{\nu}$ begins with $E$ and ends with $N$,
the number of cyclic peaks is the same as the number of valleys in
$\overline{\nu}$, with the first and last steps of $\overline{\nu}$ forming
the $w$-th cyclic peak.

$s$$1$$2$$3$$4$$5$$t$$s$$1$$2$$3$$4$$5$$t$$3$$4$$5$$1$$2$$\widetilde{G}(\nu,2)$$\overline{\nu}=E_{1}N_{1}E_{2}N_{2}E_{3}E_{4}N_{4}E_{5}N_{5}$$\overline{\nu}(2)=E_{1}E_{2}N_{2}E_{3}N_{3}E_{4}N_{4}E_{5}N_{5}$$=E_{3}E_{4}N_{4}E_{5}N_{5}E_{1}N_{1}E_{2}N_{2}$
Figure 5. A reordering of the inner vertices of $\widetilde{G}(\nu,2)$ gives
$\widetilde{G}(\overline{\nu}(2),w)$ up to a relabeling of inner vertices.

Consider the graph $G(\overline{\nu}(i),w)$, which necessarily only has
forward edges. Now $\widetilde{G}(\overline{\nu}(i),w)$ is the graph
$\widetilde{G}(\nu,i)$ up to relabeling of the vertices. Figure 5 gives an
example. We also have that
$\mathcal{F}_{\widetilde{G}(\nu,i)}\equiv\mathcal{F}_{\widetilde{G}(\overline{\nu}(i),w)}$
since changing the sign of the flow in the possible backward edge of
$\mathcal{F}_{\widetilde{G}(\nu,i)}$ is an integral equivalence (Lemma 2.2).
Therefore the reduction lemma holds for $\mathcal{F}_{\widetilde{G}(\nu,i)}$,
and reductions of the monomial $M(G(\nu,i))$ encode subdivisions of
$\mathcal{F}_{\widetilde{G}(\nu,i)}$. By the reordering of inner vertices, it
is now also immediate that the reductions of $M(\cap_{i\in S}G(\nu,i))$ encode
subdivisions of $\cap_{i\in S}\mathcal{Q}_{i}$ for any $S\subseteq[w]$.
Therefore, multiplying monomials encoding faces of codimension $k$ by
$\beta^{k}$, we obtain the following.

See 1.2

###### Proof.

By Theorem 1.1, each $S\subseteq[w]$ determines a face $\cap_{i\in
S}\mathcal{Q}_{i}$ in the simplex-subdivision of
$\mathcal{F}_{\widetilde{G}_{B}(\nu)}$ which is integrally equivalent to
$\mathcal{F}_{\cap_{i\in S}\widetilde{G}(\nu,i)}$. A monomial $M(\cap_{i\in
S}G(\nu,i))\beta^{|S|-1}$ then encodes a codimension $|S|-1$ face in the
subdivision. A reduction at a pair $x_{ij}x_{jk}$ encodes the cutting of the
simplex subdivision of $\mathcal{F}_{\widetilde{G}_{B}(\nu)}$ with the
hyperplane determined by $x_{(i,j)}=x_{(j,k)}$. Therefore, reductions of
$P_{\nu}$ encode subdivision of $\mathcal{F}_{\widetilde{G}_{B}(\nu)}$. ∎

By the integral equivalence in Lemma 3.4 we then have the following.

######  Corollary 4.6.

Reducing $P_{\nu}$ encodes subdivisions of a product of two simplices.

For each $\nu$ we have a simplex subdivision of $\Delta_{a}\times\Delta_{b}$,
for which reductions of the polynomial $P_{\nu}$ encode refinements. The
triangulations of each $\mathcal{Q}_{i}$ in Theorem 1.1 obtained with the
subdivision algebra are regular, as consequence of Proposition 4.3. It would
be interesting to know if all subdivisions obtained by the subdivision algebra
are also regular.

We now give an example of applying the extended subdivision algebra directly
to a product of two simplices $\Delta_{a}\times\Delta_{b}$.

$x_{21}x_{31}x_{41}$$x_{21}x_{31}x_{34}$$x_{21}x_{23}x_{41}$$x_{21}x_{24}x_{34}$$x_{21}x_{23}x_{24}$$x_{14}x_{24}x_{34}$$x_{14}x_{23}x_{24}$$x_{13}x_{14}x_{23}$$x_{23}x_{41}x_{43}$$x_{13}x_{23}x_{43}$
Figure 6. The dual graph of the triangulation obtained in Example 4.7. The
three connected components induced by the bolded red edges are dual graphs of
the triangulations of the three full dimensional cells in the simplex
subdivision.

######  Example 4.7.

Let $a=3$ and $b=2$. To subdivide $\Delta_{3}\times\Delta_{2}$, we first
choose a path $\nu$ from $(0,0)$ to $(3,2)$, say $\nu=NEENE$, and consider the
canoically labeled $\overline{\nu}=E_{1}N_{1}E_{2}E_{3}N_{3}E_{4}N_{4}$. Now
$I=\\{1,3,4\\}$ and $J=\\{1,2,3,4\\}$, and $I\cap J=\\{1,3,4\\}$. Cycling the
path $\overline{\nu}$ to start at its cyclic peaks we have
$\overline{\nu}(1)=E_{2}E_{3}N_{3}E_{4}N_{4}E_{1}N_{1}$,
$\overline{\nu}(2)=E_{4}N_{4}E_{1}N_{1}E_{2}E_{3}N_{3}$, and
$\overline{\nu}(3)=E_{1}N_{1}E_{2}E_{3}N_{3}E_{4}N_{4}$. From the resulting
graphs $G(\nu,i)$ for $i\in[3]$ we read the monomials
$M_{1}=x_{23}x_{34}x_{41}$, $M_{2}=x_{41}x_{13}x_{23}$, and
$M_{3}=x_{13}x_{23}x_{34}$. The polynomial $P_{\nu}$ is now given by

$P_{\nu}=\sum_{\begin{subarray}{c}S\subseteq[3]\\\
S\neq\emptyset\end{subarray}}\beta^{|S|-1}\gcd\\{M_{i}\mid i\in S\\},$

which expands to

$P_{\nu}=x_{23}x_{34}x_{41}+x_{41}x_{13}x_{23}+x_{13}x_{23}x_{34}+x_{23}x_{41}\beta+x_{23}x_{34}\beta+x_{13}x_{23}\beta+x_{23}\beta^{2}.$

For simplicity, we consider only simple reductions and therefore set
$\beta=0$. We then reduce this polynomial as follows.

$\displaystyle P_{\nu}(\beta=0)$
$\displaystyle=x_{23}x_{34}x_{41}+\mathbf{x_{13}}x_{23}\mathbf{x_{41}}+x_{13}x_{23}x_{34}$
$\displaystyle=x_{23}x_{34}x_{41}+x_{13}x_{23}x_{43}+x_{23}x_{41}x_{43}+\mathbf{x_{13}}x_{23}\mathbf{x_{34}}$
$\displaystyle=\mathbf{x_{23}x_{34}}x_{41}+x_{13}x_{23}x_{43}+x_{23}x_{41}x_{43}+x_{13}x_{14}x_{23}+x_{14}\mathbf{x_{23}x_{34}}$
$\displaystyle=x_{23}\mathbf{x_{24}x_{41}}+\mathbf{x_{24}}x_{34}\mathbf{x_{41}}+x_{13}x_{23}x_{43}+x_{23}x_{41}x_{43}+x_{13}x_{14}x_{23}+$
$\displaystyle\qquad x_{14}x_{23}x_{24}+x_{14}x_{24}x_{34}$
$\displaystyle=x_{23}x_{24}x_{21}+x_{23}x_{21}x_{41}+x_{24}x_{34}x_{21}+x_{21}\mathbf{x_{34}x_{41}}+x_{13}x_{23}x_{43}+$
$\displaystyle\qquad
x_{23}x_{41}x_{43}+x_{13}x_{14}x_{23}+x_{14}x_{23}x_{24}+x_{14}x_{24}x_{34}$
$\displaystyle=x_{23}x_{24}x_{21}+x_{23}x_{21}x_{41}+x_{24}x_{34}x_{21}+x_{21}x_{34}x_{31}+x_{21}x_{31}x_{41}+$
$\displaystyle\qquad
x_{13}x_{23}x_{43}+x_{23}x_{41}x_{43}+x_{13}x_{14}x_{23}+x_{14}x_{23}x_{24}+x_{14}x_{24}x_{34}$

Each summand in the reduced form corresponds to a simplex, with each generator
$x_{ij}$ giving the vertex $(\mathbf{e}_{i},\mathbf{e}_{j})$ of the simplex,
where $\mathbf{e}_{i}$ and $\mathbf{e}_{j}$ are the $i$-th and $j$-th standard
basis vectors in $\mathbb{R}^{4}$ and $\mathbb{R}^{3}$ respectively. The
simplex corresponding to the summand $x_{23}x_{24}x_{21}$ is the convex hull
of vertices $(\mathbf{e}_{2},\mathbf{e}_{3})$,
$(\mathbf{e}_{2},\mathbf{e}_{4})$, and $(\mathbf{e}_{2},\mathbf{e}_{1})$,
along with the cone points of the triangulation, which are
$(\mathbf{e}_{k},\mathbf{e}_{k})$ where $k\in I\cap J=\\{1,3,4\\}$. From the
reduced form we also obtain the dual graph of the triangulation, with an edge
between monomials differing by a single generator. The dual graph is shown in
Figure 6.

##  5\. The $\nu$-cyclohedral triangulations of
$\mathcal{F}_{\widetilde{G}_{B}(\nu)}$.

In this section, we use the subdivision algebra to obtain a combinatorially
interesting triangulation of $\mathcal{F}_{\widetilde{G}_{B}(\nu)}$, or
equivalently, a product of two simplices. The triangulation in question is a
geometric realization of the cyclic $\nu$-Tamari complex of [7] and is known
as the $\nu$-cyclohedral triangulation. The $\nu$-Tamari complex and cyclic
$\nu$-Tamari complex were introduced by Ceballos, Padrol, and Sarmiento in [7]
in their study of the geomtry of Tamari lattices. We introduce them here.

Given a lattice path $\nu$, label $\overline{\nu}$ with the canonical labeling
and let $I$ and $J$ be the index sets of $E$ steps and $N$ steps respectively.
A pair $(i,j)$ with $i\in I$ and $j\in J$ is said to be an arc. If the arc
$(i,j)$ satisfies $i<j$, we say that it is an increasing arc. We denote the
set of increasing arcs on $\overline{\nu}$ by
$\mathcal{A}_{\overline{\nu}}^{\mathrm{inc}}$ and the set of all arcs on
$\overline{\nu}$ by $\mathcal{A}_{\overline{\nu}}$. An arc $(i,j)$ is minimal
if $i=j$, and it is maximal if $i=1$ and $j=n$, or $j<i$ and there is no $k\in
I\cup J$ with $j<k<i$. The arcs $(1,8)$ and $(6,5)$ are the maximal arcs of
the left and right cyclic $(I,J)$-trees in Figure 7 respectively. Two arcs
$(i,j)$ and $(i^{\prime},j^{\prime})$ are said to cyclically cross if any of
the following conditions hold (up to reversing the roles of the arcs):

$\displaystyle(1)\quad i<i^{\prime}<j<j^{\prime},$ $\displaystyle(2)\quad
j^{\prime}<i<i^{\prime}<j,\quad$ $\displaystyle\quad\quad(3)\quad
j<j^{\prime}<i<i^{\prime},$ $\displaystyle(4)\quad i^{\prime}<j<j^{\prime}<i,$
$\displaystyle(5)\quad i<j^{\prime}<i^{\prime}<j,\quad$
$\displaystyle\quad\quad(6)\quad j<i<j^{\prime}<i^{\prime}.$

These are visualized in Figure 8

$\overline{\nu}=$$E_{1}$$E_{2}$$E_{3}$$N_{3}$$N_{4}$$N_{5}$$E_{6}$$N_{6}$$E_{7}$$N_{7}$$N_{8}$$\overline{\nu}=$$E_{1}$$E_{2}$$E_{3}$$N_{3}$$N_{4}$$N_{5}$$E_{6}$$N_{6}$$E_{7}$$N_{7}$$N_{8}$
Figure 7. Two cyclic $(I,J)$-trees. The left tree is also an increasing
$(I,J)$-tree.
$i$$i^{\prime}$$j$$j^{\prime}$(1)$j^{\prime}$$i$$i^{\prime}$$j$(2)$j$$j^{\prime}$$i$$i^{\prime}$(3)$i^{\prime}$$j$$j^{\prime}$$i$(4)$i$$j^{\prime}$$i^{\prime}$$j$(5)$j$$i$$j^{\prime}$$i^{\prime}$(6)
Figure 8. The six configurations of cyclically crossing arcs.

A cyclic $(I,J)$-forest is a subgraph of $K_{I,J}$ whose arcs are cyclically
non-crossing. A cyclic $(I,J)$-tree is a maximal cyclic $(I,J)$-forest. A
$(I,J)$-forest and a $(I,J)$-tree are cyclic $(I,J)$-trees and forests
respectively with only increasing arcs.

######  Definition 5.1.

The $\nu$-Tamari complex is the flag simplicial complex on increasing
$(I,J)$-forests whose minimal non-faces are pairs of crossing arcs. The cyclic
$\nu$-Tamari complex is the flag simplicial complex on cyclic $(I,J)$-forests
whose minimal non-faces are pairs of cyclically crossing arcs.

Two cyclic $(I,J)$-trees $T$ and $T^{\prime}$ are related by an increasing
flip if $T^{\prime}$ can be obtain from $T$ by replacing an arc $(i,j)\in T$
with an arc $(i^{\prime},j^{\prime})$ where $i<i^{\prime}$. This gives a cover
relation $T<_{I,J}T^{\prime}$ on cyclic $(I,J)$-trees. The cyclic $\nu$-Tamari
poset is the transitive closure of the relation $<_{I,J}$ on the set of cyclic
$(I,J)$-trees. Restricting to the set of increasing $(I,J)$-trees, the
transitive closure of $<_{I,J}$ gives the $\nu$-Tamari lattice.

We can now construct a reduction order such that the reduced form of $P_{\nu}$
encodes the cyclic $\nu$-Tamari complex. Define the length of an edge $(i,j)$
to be $i+n-j\pmod{n}$. A pair $x_{ij}x_{jk}$ form a longest pair at vertex $j$
if $x_{ij}$ and $x_{jk}$ respectively correspond with the longest incoming and
outgoing edges at $j$. The length reduction order $\rho_{\text{len}}$ is the
reduction order induced by successively reducing the longest pair
$x_{ij}x_{jk}$ with minimal $j$ at each reduction step. To see that reducing
$P_{\nu}$ according to $\rho_{\text{len}}$ gives the cyclic $\nu$-Tamari
complex, we first need a few lemmas.

A graph is said to be alternating if each of its vertices is a source or sink.
Let $D_{\overline{\nu}}$ denote the set of all maximal alternating graphs on
vertex set $I\cup J$ with forward edges $(i,j)$ satisfying $i\in I$ and $j\in
J$. Note that by maximality the graphs in $D_{\overline{\nu}}$ must be trees
and therefore have $|I\cup J|-1$ edges.

######  Lemma 5.2.

The alternating graphs in $D_{\overline{\nu}}$ are in bijection with the
increasing $(I,J)$-trees determined by $\overline{\nu}$.

###### Proof.

The bijection is given by mapping each arc $(i,j)$ in an $(I,J)$-tree to the
edge $(i,j)$ in a graph, and noting that non-crossing condition is identical
for arcs and edges. Although the minimal arcs $(i,i)$ are mapped to empty
edges, the map is a bijection as all minimal arcs appear in the
$(I,J)$-forests. ∎

######  Lemma 5.3.

The reduced forms of $M(G(\nu))$ obtained by any reduction order in which
longest pairs are reduced first at each vertex are equal.

###### Proof.

Since the facets of a triangulation determine the inner faces, it suffices to
show that the monomials of highest degree encode the graphs in
$D_{\overline{\nu}}$.

We first show that a reduction at a longest pair preserves the non-crossing
condition. Let $G$ be a non-crossing graph on $[n]$ with all edges directed
forward. Consider any vertex $j$ with its longest incoming and outgoing edges
$(i,j)$ and $(j,k)$, i.e. there are no edges $(i^{\prime},j)$ and
$(j,k^{\prime})$ with $i^{\prime}<i$ and $k<k^{\prime}$. Since no edge in $G$
crosses $(i,j)$ or $(j,k)$, and they are a longest pair, the edge $(i,k)$ does
not cross any edge in $G$. Thus each of the three graphs obtained by a
reduction at $j$ are non-crossing.

Let $R$ be a reduced form of $G(\nu)$ obtained by reducing longest pairs
first. Since the graph $G(\nu)$ is non-crossing by construction, all graphs
encoded by the monomials in $R$ are non-crossing. In addition, the graphs
obtained from $G(\nu)$ by reductions do not have multiedges, as $G(\nu)$ is
acyclic as an undirected graph. In $G(\nu)$, there is an edge for each $i\in
I\setminus J$, an edge for each $j\in J\setminus I$, and the edges on the path
through vertices in $I\cap J$. Thus the number of edges in $G(\nu)$ is $|I\cup
J|-1$. Since simple reductions preserve the number of edges, the monomials of
highest degree in $R$ encode simple alternating graphs with $|I\cup J|-1$
edges, and hence must be maximal.

Since the monomials of highest degree in a reduced form of $M(G(\nu))$
correspond with the facets of a unimodular triangulation of
$\mathcal{F}_{\widetilde{G}(\nu)}$, they are enumerated by the volume of
$\mathcal{F}_{\widetilde{G}(\nu)}$, which is the number of lattice paths
weakly above $\nu$, i.e. the $\nu$-Catalan number $\operatorname{Cat}(\nu)$.
This is also the number of $(I,\overline{J})$-trees, and therefore via the
bijection in Lemma 5.2 the monomials of highest degree in $R$ must comprise
the whole set $D_{\overline{\nu}}$. Since the inner faces of a triangulation
are determined by the facets of the triangulation, the reduced form $R$ is
determined by its monomials of highest degree. ∎

######  Proposition 5.4.

[4] The triangulation of $\mathcal{F}_{\widetilde{G}(\nu)}$ given by reducing
$M(G(\nu))$ in the reduction order $\rho_{\text{len}}$ is a geometric
realization of the cyclic $\nu$-Tamari complex.

###### Proof.

Let $R$ be the reduced form obtained from reducing $G(\nu)$ in the order
$\rho_{\text{len}}$. Let $M$ be a monomial of highest degree in $R$ and let
$G_{M}$ be its corresponding graph. Label each edge $(s,i)$ with $E_{i}$ and
each edge $(j,t)$ with $N_{j}$. As $G_{M}$ is alternating, a route in
$\widetilde{G}_{M}$ is of the form $(s,i)$, $(i,j)$, $(j,t)$ with $i\in I$,
$j\in J$, where $(i,j)$ is the empty edge if $i=j$. Define the map
$\Phi:\mathcal{R}(\widetilde{G}(\nu))\to\mathcal{A}_{\nu}$ by mapping the
route determined by the pair of edges $(E_{i},N_{j})$ to the arc $(i,j)$. Now
$\Phi$ extends to a bijection between simplicial complexes, taking faces of
the triangulation to $(I,\overline{J})$-forests. ∎

$s$$1$$2$$3$$4$$5$$t$$E_{1}$$E_{2}$$E_{3}$$E_{4}$$E_{5}$$N_{1}$$N_{2}$$N_{4}$$N_{5}$$\overline{\nu}=$$E_{1}$$N_{1}$$E_{2}$$N_{2}$$E_{3}$$E_{4}$$N_{4}$$E_{5}$$N_{5}$$s$$3$$4$$5$$1$$2$$t$$E_{3}$$E_{4}$$E_{5}$$E_{1}$$E_{2}$$N_{4}$$N_{5}$$N_{1}$$N_{2}$$\overline{\nu}(2)=$$E_{3}$$E_{4}$$N_{4}$$E_{5}$$N_{5}$$E_{1}$$N_{1}$$E_{2}$$N_{2}$$\widetilde{G}_{M}$
with  $M=x_{12}x_{32}x_{42}x_{45}$ Figure 9. A cyclic reorientation of inner
vertices corresponds with a cyclic shift of a cyclic $(I,J)$-tree. A route
through edges labeled $E_{i}$ and $N_{j}$ corresponds with the arc
$(E_{i},N_{j})$ in the $(I,J)$-tree.

Every cyclic $(I,J)$-tree has a maximal arc $(i,j)$ where $i$ and $j$ are the
indices of an $E$ step and $N$ step of cyclic peak of $\overline{\nu}$. In
this way the set of cyclic peaks of $\overline{\nu}$ naturally partition the
set of cyclic $(I,J)$-trees into $w=|I\cap J|$ disjoint sets, where each set
consists of the cyclic $(I,J)$-trees with the same maximal arc. Furthermore,
note that these $w$ sets of cyclic $(I,J)$-trees can be considered as the sets
of increasing $(I,J)$-trees induced by the paths $\overline{\nu}(i)$ for
$1\leq i\leq w$.

See 1.3

###### Proof.

The monomials in $P_{\nu}$ correspond with the graphs $G(\nu,1)$, $G(\nu,2)$,
$\ldots$, $G(\nu,w)$, along with their intersections. The reduced form of each
$M(G(\nu,\ell))$ according to $\rho_{\text{len}}$ gives a triangulation of
$\mathcal{Q}_{\ell}$ whose facets are encoded by the $(I,J)$-trees with
maximal arc determined by the $\ell$-th cyclic peak of $\nu$. Thus the
triangulation of $\mathcal{F}_{\widetilde{G}_{B}(\nu)}$ produced has facets
given by the set of cyclic $(I,J)$-trees determined by $\nu$. ∎

######  Remark 5.5.

In the case that $\nu=(NE)^{n}$, Ehrenborg, Hetyei, and Readdy [15] gave an
alternative description to $(I,J)$-trees which they called valid digraphs. The
graphs corresponding to the monomials in the reduced form of $P_{\nu}$ under
the length reduction order are a generalization of their valid graphs.

######  Corollary 5.6.

Reducing $P_{\nu}$ in the order $\rho_{\text{len}}$ gives a triangulation of
$\mathcal{F}_{G_{B}(\nu)}$ whose dual graph is the Hasse diagram of the cyclic
$\nu$-Tamari poset.

The reduction order in Example 4.7 was $\rho_{len}$, and hence the dual graph
of the resulting triangulation in Figure 6 is the Hasse diagram of the cyclic
$\nu$-Tamari poset for $\nu=NEENE$.

In the case that $\nu=E^{a}N^{b}$, the $\nu$-Tamari complex and cyclic
$\nu$-Tamari complex are the same. The length reduction order was shown in [5,
Theorem 1.3] to give a staircase triangulation in this case.

######  Remark 5.7.

When $\nu$ is the staircase path $(NE)^{n}$, reductions of $P_{\nu}$ can be
viewed as successive truncations of an $n$-simplex. The truncation order
induced by $\rho_{\text{len}}$ yields the cyclohedron, as in Figure 10.

$\mathbf{x_{12}x_{23}}$$x_{34}$$\mathbf{x_{12}x_{23}}$$x_{41}$$x_{12}x_{34}x_{41}$$x_{23}x_{34}x_{41}$$\longrightarrow$$\longrightarrow$$\cdots$$\longrightarrow$$x_{12}x_{13}x_{34}$$x_{13}x_{23}x_{34}$$x_{13}x_{23}x_{41}$$x_{12}x_{13}x_{41}$$x_{12}x_{34}x_{41}$$x_{23}x_{34}x_{41}$
Figure 10. When $\nu$ is the staircase path $(NE)^{n}$, the cylcohedron is
obtained by reducing the monomial $P_{\nu}$ in the reduction order
$\rho_{\text{len}}$.

## Acknowledgements

The author thanks Martha Yip for many inspiring conversations and helpful
suggestions.

## References

  * [1] Federico Ardila and Sara Billey  “Flag arrangements and triangulations of products of simplices”  In _Advances in Mathematics_ 214.2 Elsevier, 2007, pp. 495–524
  * [2] Federico Ardila and Mike Develin  “Tropical hyperplane arrangements and oriented matroids”  In _Mathematische Zeitschrift_ 262.4 Springer, 2009, pp. 795–816
  * [3] Welleda Baldoni and Michéle Vergne  “Kostant partitions functions and flow polytopes”  In _Transform. Groups_ 13.3-4, 2008, pp. 447–469
  * [4] Matias von Bell and Martha Yip  “The $\nu$-Tamari complex via the subdivision algebra” In preparation
  * [5] Matias von Bell, Rafael S. González D’León, Francisco A. Mayorga Cetina and Martha Yip  “A unifying framework for the $\nu$-Tamari lattice and principal order ideals in Young’s lattice” arxiv:2101.10425
  * [6] Cesar Ceballos, Arnau Padrol and Camilo Sarmiento  “Dyck path triangulations and extendability”  In _J. Combin. Theory Ser. A_ 131, 2015, pp. 187–208
  * [7] Cesar Ceballos, Arnau Padrol and Camilo Sarmiento  “Geometry of Tamari lattices in types $A$ and $B$”  In _Trans. Amer. Math. Soc._ 371.4, 2019, pp. 2575–2622
  * [8] Soojin Cho  “Polytopes of roots of type $A_{n}$”  In _Bulletin of the Australian Mathematical Society_ 59.3 Cambridge University Press, 1999, pp. 391–402
  * [9] Aldo Conca, Serkan Hosten and Rekha R Thomas  “Nice initial complexes of some classical ideals”  In _Algebraic and geometric combinatorics_ 423 Contemp. Math, 2006, pp. 11–42
  * [10] Vladimir I. Danilov, Alexander V. Karzanov and Gleb A. Koshevoy  “Coherent fans in the space of flows in framed graphs”  In _24th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2012)_ , Discrete Math. Theor. Comput. Sci. Proc., AR  Assoc. Discrete Math. Theor. Comput. Sci., Nancy, 2012, pp. 481–490
  * [11] Jesús A De Loera  “Nonregular triangulations of products of simplices”  In _Discrete & Computational Geometry_ 15.3 Springer, 1996, pp. 253–264
  * [12] Jesús A. De Loera, Jörg Rambau and Francisco Santos  “Triangulations” Structures for algorithms and applications 25, Algorithms and Computation in Mathematics  Springer-Verlag, Berlin, 2010
  * [13] Jesús A De Loera, Edward D Kim, Shmuel Onn and Francisco Santos  “Graphs of transportation polytopes”  In _Journal of Combinatorial Theory, Series A_ 116.8 Elsevier, 2009, pp. 1306–1325
  * [14] Mike Develin and Bernd Sturmfels  “Tropical Convexity”  In _Documenta Mathematica_ 9, 2004, pp. 1–27
  * [15] Richard Ehrenborg, Gábor Hetyei and Margaret Readdy  “Simion’s type B associahedron is a pulling triangulation of the Legendre polytope”  In _Discrete & Computational Geometry_ 60.1 Springer, 2018, pp. 98–114
  * [16] Rafael S. González D’León, Christopher RH Hanusa, Alejandro H Morales and Martha Yip  “Column convex matrices, $G$-cyclic orders, and flow polytopes”  In _arXiv preprint arXiv:2107.07326_ , 2021
  * [17] Mark Haiman  “A simple and relatively efficient triangulation of then-cube”  In _Discrete & Computational Geometry_ 6.3 Springer, 1991, pp. 287–289
  * [18] Lutz Hille  “Quivers, cones and polytopes” Special Issue on Linear Algebra Methods in Representation Theory  In _Linear Algebra and its Applications_ 365, 2003, pp. 215–237
  * [19] Karola Mészáros  “$h$-polynomials via reduced forms”  In _Electron. J. Comb_ 22.P4.18, 2015
  * [20] Karola Mészáros  “Pipe dream complexes and triangulations of root polytopes belong together”  In _SIAM Journal on Discrete Mathematics_ 30.1 SIAM, 2016, pp. 100–111
  * [21] Karola Mészáros  “Product formulas for volumes of flow polytopes”  In _Proceedings of the American Mathematical Society_ 143.3, 2015, pp. 937–954
  * [22] Karola Mészáros  “Root polytopes, triangulations, and the subdivision algebra I”  In _Transactions of the American Mathematical Society_ 363.8, 2011, pp. 4359–4382
  * [23] Karola Mészáros and Alejandro H Morales  “Volumes and Ehrhart polynomials of flow polytopes”  In _Mathematische Zeitschrift_ 293.3 Springer, 2019, pp. 1369–1401
  * [24] Karola Mészáros, Alejandro H Morales and Brendon Rhoades  “The polytope of Tesler matrices”  In _Selecta Mathematica_ 23.1 Springer, 2017, pp. 425–454
  * [25] Karola Mészáros, Alejandro H. Morales and Jessica Striker  “On flow polytopes, order polytopes, and certain faces of the alternating sign matrix polytope”  In _Discrete Comput. Geom._ 62.1, 2019, pp. 128–163
  * [26] Karola Mészáros and Avery St. Dizier  “From generalized permutahedra to Grothendieck polynomials via flow polytopes”  In _Algebraic Combinatorics_ 3.5, 2020, pp. 1197–1229
  * [27] David Orden and Francisco Santos  “Asymptotically efficient triangulations of the d-cube”  In _Discrete & Computational Geometry_ 30.4 Springer, 2003, pp. 509–528
  * [28] Francisco Santos  “A point set whose space of triangulations is disconnected”  In _Journal of the American Mathematical Society_ 13.3, 2000, pp. 611–637
  * [29] Bernd Sturmfels  “Grobner bases and convex polytopes”  American Mathematical Soc., 1996