% EJC papers *must* begin with the following two lines. 
\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P4.18}{22(4)}{2015}

% Please remove all other commands that change parameters such as
% margins or pagesizes.

% only use standard LaTeX packages
% only include packages that you actually need

% we recommend these ams packages
\usepackage{amsthm,amsmath,amssymb}

% we recommend the graphicx package for importing figures
\usepackage{graphicx}

% use this command to create hyperlinks (optional and recommended)
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

% use these commands for typesetting doi and arXiv references in the bibliography
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

% all overfull boxes must be fixed; 
% i.e. there must be no text protruding into the margins


% declare theorem-like environments
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{open}[theorem]{Open Problem}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{note}[theorem]{Note}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\def\i{{\it in}}
\def\out{{\it out}}

\def\In{{\it In}}
\def\Out{{\it Out}}


%\newcommand{\com}[1]{\textcolor{red}{$[\star \star \star$ #1 $\star \star \star]$}}


\def\Or{{\mathcal{O}}^{\rightarrow}}
\def\Ol{{\mathcal{O}}^{\leftarrow}}

\def\e{{\bf e}}
  %\def\e{\epsilon}
   \def\vol{{\rm vol}}
 
\def\vv{{\rm v}}
%\def\i{{\rm in }}
\def\fin{{\rm fin}}
\def\v{{\bf a}}
\def\aa{{\bf a}}
 \def\f_H{{\bf w}}
 \def\f{{\bf f}}
 \def\a{{\bf a}}
\def\R{\mathbb{R}}
\def\N{\mathbb{N}}
\def\Z{\mathbb{Z}}
\def\g{{\bf a}}
\def\inc{\textrm{inc}}
 \def\F{\mathcal{F}}
\def\O{\sigma}
\def\I{\mathcal{I}}
\def\c{{\bf c}}
\newcommand{\w} {\widetilde}

  \def\e{\epsilon}
   \def\vol{{\rm vol}}
 
\def\alt{{\rm dep}}

 \def\l{{\it i}}
 \def\dim{{\rm dim}}
 \def\x{{\bf x}}
 \def\a{\alpha}
 \def\b{\beta}
\def\R{\mathbb{R}}
\def\N{\mathbb{N}}
\def\Z{\mathbb{Z}}
 \def\F{\mathcal{F}}
 \def\P{\mathcal{P}}
\def\C{\mathcal{C}}
\def\S{\mathcal{S}}

\def\v{{\rm v}}
\def\ini{{\rm in }}
\def\fin{{\rm fin}}

\def\aa{{\bf a}}
 \def\f_H{{\bf w}}
 \def\f{{\bf f}}
 \def\a{\alpha}
\def\R{\mathbb{R}}
\def\N{\mathbb{N}}
\def\Z{\mathbb{Z}}
\def\g{{\bf a}}
\def\inc{\textrm{inc}}
 \def\F{\mathcal{F}}
 \def\P{\mathcal{P}}
\def\T{\mathcal{T}}
\def\is{{\rm InSeq}}
\def\myb{\widetilde{MACYB_n}(\mathfrak{b})}

\def\yb{\widetilde{ACYB_n}(\beta)}
\def\t{\mathcal{S}(\b)}
\def\mt{\mathcal{S}(\mathfrak{b})}

% if needed include a line break (\\) at an appropriate place in the title

\title{\bf $h$-polynomials via  reduced forms}

% input author, affilliation, address and support information as follows;
% the address should include the country, and does not have to include
% the street address 

\author{Karola M\'esz\'aros\thanks{The author was partially supported by a National Science Foundation Postdoctoral Research Fellowship  (DMS 1103933) and a National Science
  Foundation Grant  (DMS 1501059).}\\
\small Department of Mathematics\\[-0.8ex]
\small Cornell University\\[-0.8ex] 
\small Ithaca, NY 14853\\
\small\tt karola@math.cornell.edu\\
}

% \date{\dateline{submission date}{acceptance date}\\
% \small Mathematics Subject Classifications: comma separated list of
% MSC codes available from http://www.ams.org/mathscinet/freeTools.html}

\date{\dateline{Apr 7, 2015}{Oct 12, 2015}{Oct 30, 2015}\\
\small Mathematics Subject Classifications: 05E15, 05E45, 52B20}

\begin{document}

\maketitle

% E-JC papers must include an abstract. The abstract should consist of a
% succinct statement of background followed by a listing of the
% principal new results that are to be found in the paper. The abstract
% should be informative, clear, and as complete as possible. Phrases
% like "we investigate..." or "we study..." should be kept to a minimum
% in favor of "we prove that..."  or "we show that...".  Do not
% include equation numbers, unexpanded citations (such as "[23]"), or
% any other references to things in the paper that are not defined in
% the abstract. The abstract will be distributed without the rest of the
% paper so it must be entirely self-contained.

\begin{abstract}
  The flow polytope  $\F_{\widetilde{G}}$ is the set of nonnegative unit flows on the graph $\widetilde{G}$. The subdivision algebra of flow polytopes prescribes a way to dissect a flow polytope $\F_{\widetilde{G}}$  into simplices. Such a dissection is encoded by the terms of the so called reduced form of the monomial $\prod_{(i,j)\in E(G)}x_{ij}$. We prove that we can use the subdivision algebra of flow polytopes to construct not only dissections, but also regular flag triangulations of flow polytopes. We prove that reduced forms in the subdivision algebra are generalizations of $h$-polynomials of the triangulations of flow polytopes. We deduce several corollaries of the above results, most notably proving certain cases of a conjecture of Kirillov about the nonnegativity of reduced forms in the noncommutative quasi-classical Yang-Baxter algebra. 


  % keywords are optional
  \bigskip\noindent \textbf{Keywords:} flow polytope; subdivision algebra;  reduced form; triangulation; $h$-polynomial; nonnegativity; quasi-classical Yang-Baxter algebra.
\end{abstract}

 
 \section{Introduction}
 \label{sec:intro}
 
 Nonnegativity properties abound in mathematics, and whenever one arises, the most satisfying explanation of integer nonnegativity is to demonstrate what a certain nonnegative quantity  counts. The present paper is written in this spirit and explains nonnegativity properties of polynomials using geometric interpretations for their coefficients. 
 
 We study dissections of flow polytopes via the subdivision algebra, and show that we can construct  regular flag triangulations of flow polytopes using the subdivision algebra. This in turn empowers us to prove several interesting corollaries, one in particular partially proving a nonnegativity conjecture of Kirillov \cite[Conjecture 2]{k2} of certain polynomials  called reduced forms in the quasi-classical Yang-Baxter algebra. 
 
With our geometric methods  we can study reduced forms  in the subdivision algebra and the quasi-classical Yang-Baxter algebra. The latter algebra was introduced by A.N. Kirillov \cite{Kir, k2, k2014} with Schubert calculus in mind and it  is closely related to the Fomin-Kirillov algebra \cite{fk}.  The subdivision algebra has been considered by the present author under this name, as its relations encode ways to subdivide root and flow polytopes \cite{m1, m2, m-prod}. It has also been considered by Kirillov \cite{Kir, k2, k2014}  since it is the abelianization of the  quasi-classical Yang-Baxter algebra (and this is how he refers to it). The polynomials of interest in this paper arise as reduced forms in the above algebras; the reduced form 
 of a monomial in an algebra is obtained via substitution rules dictated by the relations of the algebra. 
 
 
 The essence of the subdivision algebra is that the reduced form of a monomial in it can naturally be seen as a dissection of a flow polytope corresponding to the monomial into simplices. We show that among these dissections that {the reduced form can encode} are also   {unimodular, regular and flag triangulations of flow polytopes}, see Theorem \ref{tri}. Using the connection of reduced forms to dissections 
 we show that {reduced forms are multivariate generalizations of $h$-polynomials}, see Theorem \ref{thm-h}.  
 Recall that the $h$-polynomial of a simplicial complex is a way of encoding the number of faces of each dimension.  We prove that   if we set certain variables of  reduced forms to $1$  in the subdivision algebra  we obtain the  (shifted) $h$-polynomials of regular triangulations of flow polytopes.  This result opens a new avenue for understanding reduced forms of monomials in the subdivision and related algebras.     
 We prove nonnegativity results in the subdivision algebra as a consequence of the specialized reduced form equaling the shifted $h$-polynomial, see Theorem \ref{pos}.  As a corollary  we establish a special case of Conjecture 2 of Kirillov appearing in \cite{k2} about the nonnegativity of reduced forms in  the quasi-classical Yang-Baxter algebra, see Theorem \ref{special}. We also express specialized reduced forms in terms of Ehrhart series of flow polytopes, which in turn can be seen in terms of Kostant partition functions, see Theorem \ref{thm-shell2} and Lemma \ref{thm-ehr}.   

 
 Our methods in this paper are largely geometric. In  \cite{h-poly2} we study reduced forms from the point of view of the structure of reduction trees, leaving the geometry behind. 
 
   
  The paper is organized as follows. In Section \ref{sec:def} we define flow polytopes. Next we explain how to subdivide flow polytopes and how we can encode the subdivisions with a reduction tree. Then we define the  subdivision algebra and show that the reduced form can be read off from the leaves of the  reduction tree. 
     In Section \ref{sec:tri} we show that we can use the subdivision algebra and arrive not only at a dissection of a flow polytope, but also to a triangulation of the flow polytope, in the sense of a simplicial complex. To do this we use a particular reduction order $\O$. The triangulation we obtain is regular and flag. In Section \ref{alt}    we  prove that the reduced form of a monomial in the subdivision algebra specialized at certain variables is equal to the shifted $h$-polynomial of  the aforementioned triangulation of the flow polytope of the associated to the monomial.  
      In Section \ref{sec:leaves} we   describe the full set of leaves of the reduction tree in order $\O$, or equivalently, the monomials in the reduced form of  a monomial. In
 Section \ref{sec:nonneg} we use the regularity of the triangulation we constructed to prove and interpret the nonnegativity of the coefficients of the reduced form of a monomial in the subdivision algebra as well as a special case of Conjecture 2 of Kirillov appearing in \cite{k2}.  In Section \ref{sec:ehr}   we relate reduced forms to Ehrhart series of flow polytopes, and thus  obtain a generalization of  \cite[Theorem 3.10]{k2}. We also relate reduced forms to Kostant partition functions.

 
 
 \section{Definitions and more of the story}
\label{sec:def}

\subsection{Flow polytopes and their subdivisions} Given a loopless graph $G$  on the vertex set $[n]$,  let $\ini(e)$ denote the smallest (initial) vertex of edge $e$ and $\fin(e)$ the biggest (final) vertex of edge $e$.  Let $E(G)=\{\{e_1, \ldots, e_l\}\}$   be the multiset of edges of $G$. We correspond  variables $x_{e_i}$, $i \in [l]$, to the edges of $G$, of which we think as flows.  
The {\bf flow polytope} $\F_G$ is naturally embedded into $\R^l$, where  $x_{e_i}$, $i \in [l]$, are thought of as the coordinates. $\F_G$  is defined by 

 $$x_{e_i}\geq 0, \mbox{ }i \in [l],$$

  $$1=\sum_{e \in E(G), \ini(e)=1}x_e= \sum_{e \in E(G),  \fin(e)=n}x_e,$$
  
\noindent  and for $2\leq i\leq n$
  
  $$\sum_{e \in E(G), \fin(e)=i}x_e= \sum_{e \in E(G), \ini(e)=i}x_e.$$
    
  
 The flow polytope $\F_{K_{n+1}}$, where $K_{n+1}$ is the complete graph on $n+1$ vertices,  can be thought of as the Chan-Robbins-Yuen polytope \cite{CRY}, and  has received a lot of attention, since  its volume is equal to $\prod_{k=0}^{n-2}Cat(k),$ where  $Cat(k)=\frac{1}{k+1}{2k \choose k}$ is the $k$th Catalan number. There  is no combinatorial proof of the aforementioned result;  Zeilberger \cite{Z} provided an analytical proof. For more of the story see \cite{mm}.

Flow polytopes lend themselves to subdivisions via  {\it reductions}, as explained below. A similar property of root polytopes was studied in \cite{m2, m1}.  


\begin{definition} \label{3} Given a graph $G$ on the vertex set $[n]$  containing edges $(i, j)$ and $(j, k)$, $i<j<k$, performing the {\bf reduction} on these edges of $G$ yields three graphs on the vertex set $[n]$:
  \begin{eqnarray} \label{graphs1}
E(G_1)&=&E(G)\backslash \{(j, k)\} \cup \{(i, k)\}, \nonumber \\
E(G_2)&=&E(G)\backslash \{(i, j)\} \cup \{(i, k)\},  \nonumber \\
E(G_3)&=&E(G)\backslash \{(i, j), (j, k)\} \cup \{(i, k)\}.
\end{eqnarray}


 When performing a reduction on the edges $(i, j), (j, k)$  we say that the edge $(i,j)$ is {\bf dropped} if we go towards $G_2$ or $G_3$ as in \eqref{graphs1} and  $(i,j)$ is {\bf kept} if we go towards $G_1$. Similarly, edge $(j,k)$ is dropped if we go towards $G_1$ or $G_3$ as in \eqref{graphs1} and  $(j,k)$ is  kept if we go towards $G_2$.


%Denote by $((i,j),(j,k),L)$ the reduction that took place to get from $G$ to $G_1$,  by $((i,j),(j,k),R)$ the reduction that took place to get from $G$ to $G_2$ and $((i,j),(j,k),M)$ the reduction that took place to get from $G$ to $G_3$. $L, R, M$ correspond to ``left, right, middle."
\end{definition}



%\begin{definition} When performing a reduction $(a, b, X)$, $X \in \{M, L, R\}$, we say that the edge $a$ is {\bf dropped} when $X=M, R$, and $a$ is {\bf kept} if $X=L$. Similarly, edge $b$ is dropped when $X=M, L$, and $b$ is kept if $X=R$. %We also say that an edge $e$  is {\bf derived from the edge $b$} if it resulted as a sequence of reductions involving $b$, or sums of edges of $b$, and $e$ itself is a sum of edges with $b$.  We also signal this by saying that $e$ is a $b^*$-edge.%, or $e \in b^*$. 
%\end{definition}



\begin{definition} A \textbf{reduction tree} $R_G$ of a graph $G$ is a tree with nodes labeled by graphs and such that all non-leaf nodes of $R_G$ have three children. The root is labeled by $G$. If there are two edges  $(i, j), (j, k) \in E(G)$,  $i<j<k$, on which we choose to do a reduction, then the  children of the root are labeled by  $G_1, G_2$ and $G_3$ as in (\ref{graphs1}). Next, continue this way by constructing  reduction trees for $G_1, G_2$ and $G_3$. If some graph has no edges $(i, j), (j, k)$,  $i<j<k$, then it is its own reduction tree. Note that the reduction tree $R_G$ is not unique; it depends on our  choice of edges to reduce.
However, the number of leaves (referring to the graph labeling a leaf) of all reduction trees of $G$ with a given number of edges is the same as Lemma \ref{leaves} states below. We choose a particular embedding of the reduction tree in the plane for convenience: we root it at $G$ with the tree growing downwards, and such that the left child is $G_1$, the middle child is $G_3$ and the right child is $G_2$; see Figure \ref{fig:redtree}. The leaves which have the same number of edges at the root are called \textbf{full dimensional}.
\end{definition}
 
 
\begin{figure}
\begin{center}
%\epsfysize=1.0in \epsfbox{commutative.eps}
\includegraphics[scale=.7]{redtree.pdf}
%\epsfbox{commutative.eps}
 \caption{A reduction tree of $G=([4], \{(1,2),(2,3), (3,4)\})$. The edges on which the reductions are performed are in bold. }
 \label{fig:redtree}
 \end{center}
\end{figure}


\begin{definition} \label{edges}
Let the edges of $G$ be $e_1, \ldots, e_k$, where we distinguish multiple edges. If a reduction involving edges $a=(i,j)$ and $b=(j,k)$ of $G$ is performed, then the new edge $(i,k)$ appearing in all three graphs as in \eqref{graphs1} is formally thought of as $a+b(=b+a)$. The other edges stay unchanged. To get to nodes $G_1$ and $G_2$  of $R_G$ we iterate this process, thereby expressing the edges of any node as a sum of edges of the graph being the root of the reduction tree. Two edges $c$ and $d$ in the graphs  $G_1$ and $G_2$, respectively, are the same, if they are the sum of exactly the same edges of $G$. The intersection of two graphs $G_1$ and $G_2$ in a reduction tree $R_G$ is $G_1\cap G_2=(V(G), E(G_1)\cap E(G_2))$, where if $e \in E(G_1)\cap E(G_2)$ then as explained above $e$ is the sum of the same edges of $G$ in both $G_1$ and $G_2$. See Figure \ref{fig:def3} for an illustration.
\end{definition}

\begin{figure}
\begin{center}
%\epsfysize=1.0in \epsfbox{commutative.eps}
\includegraphics[scale=.9]{def3.pdf}
%\epsfbox{commutative.eps}
 \caption{The edges of the nodes of a reduction tree of $G$ are considered as formal sums of the edges of $G$.}
 \label{fig:def3}
 \end{center}
\end{figure}


\begin{lemma} \label{leaves} \cite{m2} Given two distinct reduction trees of $G$, let $r^1_k$ and $r^2_k$ be the number of leaves with $k$ edges is them, respectively. Then, $r^1_k=r^2_k$. 
  \end{lemma}
 
 
 
\begin{definition}  The {\bf augmented graph} ${\widetilde{G}}$ of $G=([n], E)$ is ${\widetilde{G}}=([n]\cup \{s, t\}, \widetilde{E})$, where $s$ (source) is the smallest, $t$ (target/sink) is the biggest vertex of  $[n]\cup \{s, t\}$, and $\widetilde{E}=E\cup \{(s, i), (i, t) | i \in [n]\}$.  Denote by $\mathcal{P}(\widetilde{G})$ the set of all maximal paths in $\widetilde{G}$, referred to as \textbf{routes}. It is well known that the unit flows sent along the routes in $\mathcal{P}(\widetilde{G})$ are the vertices of $\mathcal{F}(\widetilde{G})$ \cite[Section 13.1a]{schrijver}. 
 \end{definition}


\begin{definition} \label{leaf} Consider a node $G_1$ of the reduction tree $R_G$, where each edge of $G_1$ is considered as a sum of the edges of $G$. The  map $m:E(G_1)\rightarrow \mathcal{P}(\widetilde{G})$ takes an edge $(v_1, v_2)=e=e_{i_1}+\cdots+e_{i_l}$, $e \in G_1$, $e_{i_j} \in E(G)$, $j \in [l]$, to the route $(s, v_1), e_{i_1},\ldots,e_{i_l}, (v_2, t)$. Then the vertices of $\F_{\widetilde{G_1}}$  with respect to $G$  are the unit flows along the  the routes that are in the image of $m$ and the routes of the form $(s,v), (v,t)$, where $v$ is any vertex of $G$.  In case $G_1$ is not a node of the reduction tree $R_G$, but it is  an intersection of  nodes of $R_G$, so that each edge of $G_1$ can still be considered as a sum of the edges of $G$, we still define $\F_{\widetilde{G_1}}$ as above. This definition of  $\F_{\widetilde{G_1}}$ is of course with respect to $G$, and this is understood from the context. For an example see Figure \ref{fig:def5}
\end{definition}

  \begin{figure}
\begin{center}
%\epsfysize=1.0in \epsfbox{commutative.eps}
\includegraphics[scale=.99]{def5.pdf}
%\epsfbox{commutative.eps}
 \caption{The graph $G_1$ is a node of the reduction tree give in Figure \ref{fig:def3}. The flow polytope corresponding to this node of the reduction tree is the convex hull of the points given by the unit flows on the bold routes as well as unit flows given along routes of the form $(s,v), (v,t)$, where $v\in [4]$. This flow polytope is part of a dissection of the flow polytope of the graph labeling the root, as explained in Lemma ~\ref{red}.}
 \label{fig:def5}
 \end{center}
\end{figure}


Using the above definitions the proof of  the following lemma is an easy exercise.

\begin{lemma}{ \cite[Proposition 1]{m-prod},\cite[Proposition 4.1]{mm}, \cite{p, S}}
 \label{red} Given a graph $G$ on the vertex set $[n]$ and   $(i, j), (j, k) \in E(G)$,   for some $i<j<k$,  and $G_1, G_2, G_3$ as in \eqref{graphs1} and $ \F_{{\widetilde{G}_i}}$, $i \in [3]$, as in Definition \ref{leaf} we have  $$\F_{{\widetilde{G}}}=\F_{{\widetilde{G}_1}} \bigcup \F_{{\widetilde{G}_2}},  \F_{{\widetilde{G}_1}} \bigcap \F_{{\widetilde{G}_2}}=\F_{{\widetilde{G}_3}} \text{ and } \F_{{\widetilde{G}_1}}^\circ \bigcap \F_{{\widetilde{G}_2}}^\circ=\varnothing,$$
 

 
 \noindent where $\F_{{\widetilde{G}}}$, $\F_{{\widetilde{G}_1}}$, $\F_{{\widetilde{G}_2}}$ are of the same dimension $d-1$, $\F_{{\widetilde{G}_3}}$ is $d-2$ dimensional,  and  $\mathcal{P}^\circ$ denotes the interior of $\mathcal{P}$.
\end{lemma}

The essence of Lemma  \ref{red} is that when we replace $G$ by the three graphs $G_1, G_2, G_3$ we dissected $\F_{{\widetilde{G}}}$ into polytopes $\F_{{\widetilde{G}_1}}$ and $\F_{{\widetilde{G}_2}}$ and they intersect along $\F_{{\widetilde{G}_3}}$. Iterating this, we obtain that the flow polytopes corresponding to the leaves of a reduction tree of $G$ as defined in Definition \ref{leaf} are the interior simplices of a  dissection of the flow polytope $\F_{{\widetilde{G}}}$.


 
% \begin{theorem} {\cite{m-prod, mm}} \label{norvol} The normalized volume of $\F_{{\widetilde{G}}}$ is equal to the number of full dimensional  leaves of the reduction tree $R_G$.
 %\end{theorem}
 
\subsection{Encoding subdivisions by relations} Note that the reduction of graphs given in \eqref{graphs1} can be encoded as the following relation:

\begin{equation}x_{ij}x_{jk}=x_{ik}x_{ij}+x_{jk}x_{ik}+\b x_{ik},  \mbox{ for }1\leq i<j<k\leq n. \end{equation}


Namely, interpreting the double indices of the variables $x_{ij}$ as edges, the monomial $x_{ij}x_{jk}$ picks out two edges $(i,j), (j, k)$, $i<j<k$, and replaces it with three monomials, corresponding to operation on graphs  \eqref{graphs1}. The variable $\beta$ is simply a placeholder, indicating that the number of edges in the third graph is one less than in the other graphs

These relations give rise to what we call the {\it subdivision algebra}. 

\begin{definition} The associative \textbf{subdivision algebra}, denoted by $\t$, is an associative algebra, over the ring of polynomials $\Z[\b]$, generated by the set of elements $\{x_{ij} : 1 \leq i<j \leq n\}$, subject to the relations:

(a) $x_{ij}x_{kl}=x_{kl}x_{ij},$ if  $i<j$, $k<l$,

(b) $x_{ij}x_{jk}=x_{ik}x_{ij}+x_{jk}x_{ik}+\b x_{ik},$ if $1\leq i<j<k\leq n$.

\end{definition}


The algebra $\t$ has been studied  in the context of root polytopes \cite{m2}. 


\begin{definition} \label{rf} Given a monomial $M$  in $\t$, its reduced form is defined as follows.  Starting with $p_0=M$, produce a sequence of polynomials $p_0, p_1, \ldots, p_m$ in the following fashion.  To obtain $p_{r+1}$ from $p_r$,  choose a monomial of   $p_r$ which  is divisible by $x_{ij}x_{jk}$, for some $i,j,k$, and replace the factor  $x_{ij}x_{jk}$ in this monomial   with   $x_{ik}x_{ij}+x_{jk}x_{ik}+\b x_{ik}$. Note that   $p_{r+1}$   has two more monomials than $p_r$. Continue  this process until   a  polynomial  $p_m$  is obtained, in which  no monomial is divisible by  $x_{ij}x_{jk}$, for any $i,j,k$.  Such a polynomial $p_m$  is a {\bf reduced form} of $M$. Note that we allow the use of the commutation relations  in this process.
\end{definition}


A possible sequence of reductions in algebra $\t$ yielding a reduced form of $x_{12}x_{23}x_{34}$ is given by


\begin{eqnarray} \label{ex1}
 x_{12} \mbox {\boldmath$  x_{23}x_{34}$} & \rightarrow & \mbox{\boldmath$x_{12}$}x_{24}\mbox{\boldmath$x_{23}$}+\mbox{\boldmath$x_{12}$}x_{34}\mbox {\boldmath$x_{24}$}+\beta \mbox {\boldmath$x_{12}x_{24}$} \nonumber \\
& \rightarrow& \mbox {\boldmath$ x_{24}$} x_{13}\mbox {\boldmath$x_{12}$}+x_{24}x_{23}x_{13}+  \beta x_{24}x_{13}+x_{34}x_{14}x_{12}+x_{34}x_{24}x_{14} \nonumber \\
& &+\beta x_{34}x_{14}+\beta x_{14}x_{12}+\beta x_{24}x_{14}+\beta^2 x_{14} \nonumber \\
& \rightarrow  &x_{13}x_{14}x_{12}+x_{13}x_{24}x_{14}+\beta x_{13}x_{14}+x_{24}x_{23}x_{13}+\beta x_{24}x_{13}\nonumber \\
& & +x_{34}x_{14}x_{12}+x_{34}x_{24}x_{14}+\beta x_{34}x_{14}+\beta x_{14}x_{12}+\beta x_{24}x_{14}\nonumber \\
& &+\beta^2 x_{14}
\end{eqnarray}

 
\noindent where the pair of variables on which the reductions are performed is in boldface. The reductions are performed on each monomial separately.




Given a monomial $M$ we can encode it by a graph $G_M$, simply by letting the edges of $G_M$ be the given by the indices of the variables in $M$. Denote a reduced form of $M$  in $\t$ by $Q_{G_M}^{\t}(\x; \b)$. Note that the reduced form of $M$ is not unique, so if we wanted to specify the reduced form exactly, we would also need to specify a reduction tree for $G$. When writing $Q_{G_M}^{\t}(\x; \b)$ we pick an arbitrary reduced form at hand.  If in the reduced forms we set $\x=(1, \ldots, 1)$, then in the notation we omit $\x$:  
$Q_{G_M}^{\t}(\b)$.  We will show later that $Q_{G_M}^{\t}(\b)$ is independent of the choice of reduction tree, thus $Q_{G_M}^{\t}(\b)$ is well-defined as is.


It is easy to see that by definition, a reduced form of a monomial in the subdivision algebra can be read off from the leaves of the reduction tree of the corresponding graph. With this and Lemma \ref{red} in mind, it is no surprise that we can  prove results about reduced forms of monomials in the algebras using flow polytopes.

Recall  that a reduced form of a monomial in  $\t$ is not necessarily unique, which could be a desirable property. Amazingly, there is  a noncommutative algebra, denoted $\yb$, which is much like $\t$, yet in which the reduced forms are unique. The latter statement was proved  in \cite{m2}.  It was A.N. Kirillov \cite{k2, k2014} who introduced $\yb$ and shed the first light on its rich combinatorial structure. The paper \cite{h-poly2}  addresses more of the story of subdivision algebras as well as the story of  $\yb$.


 \section{Triangulating flow polytopes}
 \label{sec:tri}



In this section we prove  that we can use the subdivision algebra to obtain triangulations of every flow polytope $\F_{\widetilde{G}}$. A priori this is far from clear -- we are only guaranteed dissections of flow polytopes, but not the simplicial complex structure.  Moreover, the triangulation we obtain is flag and regular, and thus shellable. We construct our special triangulation by picking a specific reduction order $\O$ on our graph $G$ and utilizing the properties of $\O$ to prove properties about the leaves of the reduction tree $R_G^{\O}$ obtained using $\O$.  We then note that there is a whole class of orders for which our arguments work, but for clarity we lay out the argument for $\O$ first. 


\subsection{A family of orders $\F(\O)$}
\label{sec:orders}

  Given an arbitrary graph $G$ on the vertex set $[n]$, put a total order on the set of incoming and as well as a total order set of outgoing edges at each vertex $1<v<n$ (thus we consider each edge twice here, once as an incoming edge and once as an outgoing edge).
 Do the reductions in $G$ proceeding from the smallest vertex towards the greatest in order. Look for the smallest vertex $v$ which is nonalternating, that is that has both an edge $(a, v)$ and an edge $(v, b)$ incident to it, with $a<v<b$. (Two edges $(a, v)$ and   $(v, b)$ are \textbf{non-alternating} if $a<v<b$.) Look at the incoming  and outgoing edges at $v$,  $(a, v)$  and  $(v, b)$, which are smallest in the ordering of the incoming and outgoing edges, respectively. Do the reduction on $(a, v)$  and  $(v, b)$. In the three obtained graphs the relative ordering of the edges stays the same, with the new edge $(a, b)$ either taking the place of   $(a, v)$  or  $(v, b)$ if these were dropped, or directly preceeding them when they are kept.  Continue in this fashion on each leaf of the partial reduction tree ultimately arriving to the reduction tree $R_G$ with all leaves alternating graphs, that is all of their vertices are alternating.  Let $\O$ be the order where the initial ordering of the incoming and  outgoing edges at each vertex is such that the topmost is the smallest, then the next topmost, etc. See Figure \ref{fig:sigma} for an example of this ordering. All results of this paper generalize for any order in $\F(\O)$, but for simplicity we state and prove them for $\O$ only.
 
 
\begin{figure}
\begin{center}
%\epsfysize=1.0in \epsfbox{commutative.eps}
\includegraphics[scale=.9]{sigma.pdf}
%\epsfbox{commutative.eps}
 \caption{The ordering of the incoming and outgoing edges at each vertex from topmost to bottom.}
 \label{fig:sigma}
 \end{center}
\end{figure}




The main result of this section is: 


\begin{theorem} \label{tri} The simplices corresponding to the full dimensional leaves of $R_G^{\O}$  yield the top dimensional simplices in a regular and flag triangulation of $\F_{\widetilde{G}}$. Moreover, lower dimensional simplices of this triangulation which are not contained in the boundary of $\F_{\widetilde{G}}$ are obtained from the (not  full dimensional) leaves of $R_G^{\O}$.
\end{theorem}

\proof The proof follows from Theorem \ref{k}, Lemma \ref{flag} and Proposition \ref{coh}.
\qed


\medskip


Next we explain Theorem \ref{k} and prove Proposition \ref{coh}.  



\subsection{Coherent routes, cliques and triangulation of flow polytopes} Given a graph $G$ on the vertex set $[n]$ with edges oriented from smaller to bigger vertices, the vertices of the flow polytope $\F_G$ correspond to integer flows  of size one on maximal directed paths from the source ($1$) to the sink ($n$). Following \cite{kosh} we call such maximal paths \textbf{routes}. The following definitions  follow \cite{kosh}. Fix a \textbf{framing} at each inner vertex $v$ (that is a vertex that is not a source or a sink) of $G$, which is the linear ordering $\prec_{\i(v)}$ on the set of incoming edges $\i(v)$ to $v$  and the linear ordering $\prec_{\out(v)}$ on the set of  outgoing edges $\out(v)$ from $v$.  We call a graph with a framing at each inner vertex framed. For a framed graph $G$ and an inner vertex $v$ we denote by $\In(v)$ and by $\Out(v)$ the set of maximal paths ending in $v$ and   the set of maximal paths starting at $v$, respectively. We define the order $\prec_{\In(v)}$ on the paths in $\In(v)$ as follows. If $P, Q \in \In(v)$  then let $w$ be the largest vertex after which $P$ and $Q$ coincide and before which they differ. Let $e_P$ be the edge of $P$ entering $w$ and $e_Q$ be the edge of $Q$ entering $w$. Then $P \prec_{\In(v)} Q$ if and only if $e_P \prec_{\i(w)} e_Q$. The linear order $\prec_{\Out(v)}$ on $\Out(v)$ is defined analogously. 

Given a route $P$ with an inner vertex $v$ denote by $Pv$ the maximal subpath of $P$ entering $v$ and by $vP$ the maximal subpath of $P$ leaving $v$. We say that the routes $P$ and $Q$ are \textbf{coherent at a vertex} $v$ which is an inner vertex of both $P$ and $Q$ if the paths $Pv, Qv$ are ordered the same way as $vP, vQ$; e.g., if 
$Pv \prec_{\In(v)}Qv$ and 
$vP \prec_{\Out(v)}vQ$. 
We say that routes $P$ and $Q$ are \textbf{coherent} if they are coherent at each common inner vertex. We call a set of mutually coherent routes a \textbf{clique}. The following theorem is a special case of \cite[Theorems 1 \& 2]{kosh}.

\begin{theorem}  \cite[Theorems 1 \& 2]{kosh} \label{k} Given a framed graph $G$, taking the convex hulls of the vertices corresponding to the routes in maximal cliques yield the top dimensional simplices in a regular triangulation of $\F_G$. Moreover, lower dimensional simplices of this triangulation are obtained as convex hulls of the vertices corresponding to the routes in (not  maximal) cliques.
\end{theorem}

\begin{lemma} \label{flag} The triangulation described in Theorem \ref{k} is flag.
\end{lemma}

\proof Consider a  non-face $N$ of the triangulation that is of cardinality greater than $2$. By Theorem \ref{k} the vertices of $N$ are routes that are not coherent; in particular there are two routes $P$ and $Q$ which yield vertices of $N$ and are not coherent. Since $P$ and $Q$ are not coherent, they constitute a non-face. Therefore, all minimal non-faces of the triangulation described in Theorem \ref{k} are of size $2$, and therefore the triangulation is flag.
\qed

Now we are ready to prove the proposition which together with Theorem \ref{k} and Lemma \ref{flag} implies Theorem \ref{tri}. We define the framing $\widetilde{\O}$ on $\widetilde{G}$ as the ordering $\O$ on the edges of $G$, that is, the incoming edges are ordered top to bottom and the outgoing edges are also ordered top to bottom, and the edges of the form $(s, i)$ and $(i, t)$, for $i \in [n]$, are always last in the orderings. See Figure \ref{fig:frame} for an example.



\begin{figure}
\begin{center}
%\epsfysize=1.0in \epsfbox{commutative.eps}
\includegraphics[scale=.9]{framing.pdf}
%\epsfbox{commutative.eps}
 \caption{Framing $\widetilde{\O}$ on $\widetilde{G}$ with $G=([4], \{\{(1,2), (1,2), (1,3), (2,3), (2,4), (3,4)\}\})$.}
 \label{fig:frame}
 \end{center}
\end{figure}

\begin{proposition} \label{coh} The set of vertices of the simplices corresponding to the leaves of $R_G^{\O}$ form a clique of mutually coherent paths in $\widetilde{G}$ with the framing $\widetilde{\O}$. 
\end{proposition}

\proof Suppose that to the contrary, there are two vertices of a simplex corresponding to a leaf of $R_G^{\O}$, which correspond to non-coherent routes $P$ and $Q$ in $\widetilde{G}$. Suppose that $P$ and $Q$ are not coherent at the common inner vertex $v$. Suppose that the smallest vertex after which $Pv$ and $Qv$ agree is $w_1$ and the largest vertex before which $vP$ and $vQ$ agree is $w_2$. Let the edges incoming to $w_1$ be $e_P^1$ and $e_Q^1$ for $P$ and $Q$, respectively, and let  the edges outgoing from $w_2$ be $e_P^2$ and $e_Q^2$ for $P$ and $Q$, respectively. Since $P$ and $Q$ are not coherent at $v$, this implies that either $e_P^1\prec_{\i(w_1)} e_Q^1$ and $e_Q^2\prec_{\out(w_2)} e_P^2$ or $e_Q^1\prec_{\i(w_1)} e_P^1$ and $e_P^2\prec_{\out(w_2)} e_Q^2$. We also have that the segments of $P$ and $Q$ between $w_1$ and $w_2$ coincide. Note that since the edges of the form $(s, i)$ and $(i, t)$, $i \in [n]$, are last in the linear orderings of the incoming and outgoing edges, it follows that at most one of the edges $e_P^1$ and $e_P^2$ and at most one of the edges $e_Q^1$ and $e_Q^2$ could be incident to $s$ or $t$. We consider several cases based on whether any of $e_P^1, e_P^2, e_Q^1, e_Q^2$ are incident to $s$ or $t$. Denote by $p$ the sum of edges between $w_1$ and $w_2$ on $P$. If none of $e_P^1, e_P^2, e_Q^1, e_Q^2$ are incident to $s$ or $t$, then after a certain number of reductions executed according to $\O$ we are about the perform the reduction $(*(e_{\bar{Z}}^1+p), e_Z^2)$, where $*(e_{\bar{Z}}^1+p)$ denotes the sum of edges left of $w_1$ that are edges in $\bar{Z}$ not incident to $s$ (including $e_{\bar{Z}}^1$ in particular) and  $p$,  $\{\bar{Z}, Z\}=\{P, Q\}$. Note, however, that after executing this reduction we have to drop either the edge $*(e_{\bar{Z}}^1+p)$ or the edge $e_Z^2$. However, if  the former were true, it would make it impossible for $*(e_{\bar{Z}}^1+p)+e_{\bar{Z}}^2$ to be a subsum in an edge of the leaf we are considering, which it has to be in order for $\bar{Z}$ to be a route giving a vertex of the simplex we are considering. The latter on the other hand would make it impossible for $*(e_{Z}^1+p)+e_{{Z}}^2$ to be a subsum in an edge of the leaf we are considering, where  $*(e_{{Z}}^1+p)$ denotes the sum of edges left of $w_1$ that are edges in ${Z}$ not incident to $s$. However then  ${Z}$ cannot be a route giving a vertex of the simplex we are considering. Thus we see that $Z$ and $\bar{Z}$, aka, $P$ and $Q$, cannot be incoherent in this way. It follows that we need to consider the possibilities where some of $e_P^1, e_P^2, e_Q^1, e_Q^2$ are incident to $s$ or $t$. One can construct  similar arguments to the above in all those cases. 
\qed


\section{Reduced forms are $h$-polynomials} 
\label{alt} 

In this section we show that for a graph $G$ the reduced form of the monomial $m[G]=\prod_{(i,j) \in E(G)}x_{ij}$ can be seen as the shifted $h$-polynomial of a unimodular triangulation of the flow polytope  $\F_{\widetilde{G}}$.




\begin{definition} Let $\C$ be a $d-1$ dimensional simplicial complex.  The \textbf{$f$-vector} of $\C$ is $$f(\C)=(f_{-1}, f_0, \ldots, f_{d-1}),$$ where $f_i=f_i(\C)$ be the number of $i$-dimensional simplices in $\C$. By convention, $f_{-1}=1$ unless $\C=\varnothing$, in which case $f_{-1}=0$. The \textbf{$h$-vector} of $\C$ is $h(\C)=(h_0, h_1, \ldots, h_d)$, defined by 

\begin{equation} \label{f-h} \sum_{i=0}^d f_{i-1}(x-1)^{d-i}=\sum_{i=0}^d h_{i}x^{d-i}.\end{equation}

Define the \textbf{$h$-polynomial} of a simplicial complex $\C$ to be 

\begin{equation} h(\C, \x)=\sum_{i=0}^d h_{i}x^{i}.
\end{equation}

\end{definition}


\begin{lemma} \label{l-h-poly} \cite{Stcom} For a simplicial complex $\C$ we have:
\begin{equation} \label{h-poly} h(\C, \x)=\sum_{F \in \C}x^{\#F}(1-x)^{d-\#F}.
\end{equation}
\end{lemma}



The main result of this section is the following theorem. 

\begin{theorem} \label{thm-h} We have 
\begin{equation}Q_G^{\t}(\b)=h(\C, \b+1),  \end{equation}where $\C$ is any unimodular triangulation of ${\F_{\widetilde{G}}}$.
\end{theorem}

We illustrate the theorem on an example in Figure \ref{h-ex}. 

\begin{figure}
\begin{center}
%\epsfysize=1.0in \epsfbox{commutative.eps}
\includegraphics[scale=.8]{h-ex.pdf}
%\epsfbox{commutative.eps}
 \caption{On the left is a reduction tree of $G=([2], \{(1,2),(2,3)\})$ with the monomials corresponding to the graphs noted and a description of the corresponding triangulation $\mathcal{C}$. On the right is the reduced form corresponding to the reduction tree and the (shifted) $h$-polynomial of $\mathcal{C}$. As in Theorem \ref{thm-h} we get $Q_G^{\t}(\b)=h(\C, \b+1)$.}
 \label{h-ex}
 \end{center}
\end{figure}


To prove Theorem \ref{thm-h}, we use the following lemma, which is implicit in \cite{Stcom}.  For completeness, we include a proof of it. 

\begin{lemma} \label{pure} Let $\C$ be a $(d-1)$-dimensional    simplicial complex homeomorphic to a ball and $f_i^\circ$ be the number of interior faces of $\C$ of dimension $i$. Then 
\begin{equation} \label{h} h(\C, \beta+1)=\sum_{i=0}^{d-1} f_i^\circ \beta^{d-1-i}
\end{equation}
\end{lemma}
\proof We have that 

$$h(\C, \beta+1)=\sum_{F\in \C} (\beta+1)^{\#F}(-\beta)^{d-\#F}=\sum_{i=-1}^{d-1}f_i(\beta+1)^i (-\beta)^{d-i-1}.$$

Thus, \eqref{h} is equivalent to \begin{equation} \label{eq}\sum_{i=-1}^{d-1}f_i(\beta+1)^i (-\beta)^{d-i-1}=\sum_{i=0}^{d-1} f_i^\circ \beta^{d-1-i},\end{equation} which is what we proceed to prove now.
For brevity, denote the left hand side of \eqref{eq} by $LHS$ and the right hand side by $RHS$. Then we see that 

$$[\beta^d]LHS=(-1)^d+\sum_{i=0}^{d-1}f_i(-1)^{d-i-1} {{i+1} \choose 0}.$$ 

For $j \in [d]$ we have that 

$$[\beta^{d-j}]LHS=\sum_{i=j-1}^{d-1}f_i(-1)^{d-i-1} {{i+1} \choose j}.$$ 

On the other hand, $[\beta^d]RHS=0$ and  for $j \in [d]$ we have $[\beta^{d-j}]RHS=f_{j-1}^\circ$. Thus,  \eqref{eq}  is equivalent to

 \begin{equation} \label{eq1} (-1)^d+\sum_{i=0}^{d-1}f_i(-1)^{d-i-1} {{i+1} \choose 0}=0  \end{equation} 
and for $j \in [d]$ 


 \begin{equation} \label{eq2} \sum_{i=j-1}^{d-1}f_i(-1)^{d-i-1} {{i+1} \choose j}=f_{j-1}^\circ.\end{equation} 

Note that \eqref{eq1} is the familiar Euler characteristic expression of a simplicial complex that is homeomorphic to a  ball. To prove 
\eqref{eq2}  we interpret its  
left hand side   as an inclusion exclusion formula for $f_{j-1}^\circ$. Indeed, $f_{d-1} {{d}\choose {j}}$ is the number of $(j-1)$-faces of the $f_{d-1}$ top dimensional simplices in $\C$, with overcounting. To correct for the overcounting we substract  $f_{d-2} {{d-1}\choose {j}}$, which is the number of $(j-1)$-faces of the $f_{d-2}$ $(d-2)$-simplices of $\C$. Note that here we therefore also take out all $(j-1)$-faces that are on the boundary of $\C$. Again, we have oversubstracted, so we add back $f_{d-3} {{d-2}\choose {j}}$, etc., to arrive to 
$f_{j-1}^\circ$. We used that $\C$ is a pure simplicial complex when we assumed that all $(j-1)$-faces are a face of a $(d-1)$-face. \qed



 
\bigskip

\noindent \textit{Proof of Theorem \ref{thm-h}.}
Note that, by definition, the reduced form $Q_G^{\t}(\b)$ read off from the reduction tree $R_G^{\O}$, which yields the unimodular triangulation $\C^{\O}$, can be written as

\begin{equation}\label{uni} Q_G^{\t}(\b)=\sum_{i=1}^{d-1} f^\circ_i \b^{d-1-i},\end{equation}where $\C^{\O}$ is $d-1$ dimensional and $f^\circ_i$ is the number of leaves of $R_G^{\O}$ yielding an $i$-dimensional simplex. The notation $f^\circ_i$ signifies that the union of the open simplices corresponding to the leaves of a reduction tree yield the open polytope $\F_{\widetilde{G}}$.  By Lemma \ref{pure} we have that 
\begin{equation}\sum_{i=1}^{d-1} f^\circ_i \b^{d-1-i}=h(\C^{\O}, \b+1).\end{equation}Since by Lemma \ref{leaves} we know that $Q_G^{\t}(\b)$ does not depend on the particular reduction tree, we are done. \qed

\section{A description of the leaves of $R_G^{\O}$}
\label{sec:leaves}

In this section we  describe all the leaves of the reduction tree $R_G^{\O}$ in terms of shellings of the triangulation obtained from $R_G^{\O}$ as in Theorem \ref{tri}. % from Theorem \ref{thm-shell}. We will use the ideas of this section to introduce a refinement of the $h$-vector for the triangulation arising from  $R_G^{\O}$ as well as to prove several nonnegativity results about reduced forms, including two conjectures of Kirillov. 
Since we know that these triangulations are regular, it follows that they are also shellable.  


\begin{theorem} \label{thm-shell2}  Let $\F_{\widetilde{F_1}}, \ldots, \F_{\widetilde{F_l}}$ be a shelling order of the simplicial complex arising from $R_G^{\O}$. Let $$P_i:=\{\{Q_1^i, \ldots, Q_{f(i)}^i\}\}=\{\{F_i \cap F_j \mid 1\leq j<i, |E(F_i \cap F_j)|=|E(F_i)|-1\}\}.$$  Then 
\begin{equation}\label{formal} \sum_{i=1}^l \prod_{j=1}^{f(i)} (F_i+Q_j^i)\end{equation}

\noindent is the formal sum of the  set of the leaves of $R_G^{\O}$, where the product of graphs is their intersection. If $f(i)=0$ we define  $\prod_{j=1}^{f(i)} (F_i+Q_j^i)=F_i$.

\end{theorem} 


Before proving Theorem \ref{thm-shell2}, we record  a few properties of flow polytopes that easily follow from the above considerations and from the fact that the dimension of $\F_G$ is $|E(G)|-|V(G)|+1$ \cite{BV2}. In both lemmas the meanings of 
$\F_{\widetilde{H}}$ for a node $H$ of $R_G^{\O}$ or intersection of such nodes is as in Definition \ref{leaf}, which is the key to the proofs that are left to the interested reader. 


\begin{lemma} \label{coord} Let $G_1$ and $G_2$ be two leaves of $R_G^{\O}$. Then 

\begin{equation}\label{int}  \F_{\widetilde{G_1}}\cap \F_{\widetilde{G_2}}=\F_{\widetilde{G_1\cap G_2}}.\end{equation}Moreover, $G_1\cap G_2$ is a leaf of $R_G^{\O}$ if and only if $\F_{\widetilde{G_1}}\cap \F_{\widetilde{G_2}}$ is not contained in the boundary of $\F_{\widetilde{G}}$. 
\end{lemma}


\begin{lemma} \label{dimension}  Let $G_1$ and $G_2$ be two leaves of $R_G^{\O}$. The dimension of  $\F_{\widetilde{G_1\cap G_2}}$ is $|E(G_1\cap G_2)|+|V(G_1\cap G_2)|-1$.
\end{lemma}

%\begin{lemma}  \label{subsets} Let $G_1, G_2$ and $G_3$ be three leaves of $R_G^{\O}$ so that $G_1\cap G_2 \subset G_1 \cap G_3$. Then 

%\begin{equation}\label{int1} \F_{\widetilde{G_1\cap G_2}} \subset  \F_{\widetilde{G_1\cap G_3}}.\end{equation}  
%\end{lemma}


\noindent \textit{Proof of Theorem \ref{thm-shell2}.}  By Lemmas \ref{coord} and \ref{dimension} we see that if $\F_{\widetilde{F_1}}, \ldots, \F_{\widetilde{F_l}}$ is a shelling order, then the set of facets on which $\F_{\widetilde{F_i}}$ attaches to $\F_{\widetilde{F_1}}, \ldots, \F_{\widetilde{F_{i-1}}}$ is $\{\F_{\widetilde{Q}} \mid Q \in P_i\}$. Moreover, since the intersection of two top dimensional simplices of a triangulation of  $\F_{\widetilde{G}}$ is not contained in the boundary of  $\F_{\widetilde{G}}$, it follows that every element of $P_i$, $i \in [l]$, appears in $R_G^{\O}$ by the second part of Lemma \ref{coord} (and it is a leaf since it is the intersection of two alternating graphs, so it is alternating itself).  Using this same argument repeatedly and the fact that we can built up the polytope piece by piece by following the shelling, we obtain Theorem \ref{thm-shell2}. 
\qed




\section{Nonnegativity results about  reduced forms}
\label{sec:nonneg}

This section is devoted to two nonnegativity results, which are consequences of the above considerations.  

\begin{theorem} \label{pos} The polynomial $Q_G^{\t}(\beta-1)$ is  a polynomial in $\b$ with nonnegative coefficients.
\end{theorem}

\proof Recall that by Theorem \ref{thm-h} we have that 
\begin{equation}Q_G^{\t}(\b-1)=h(\C, \b),  \end{equation}where $\C$ is a unimodular triangulation of    $\F_{\widetilde{G}}$. Let $\C$ be the abstract  simplicial complex obtained from $R_G^{\O}$, as in Theorem \ref{tri}. Since by Theorem \ref{tri} this triangulation is regular, and therefore it is shellable,  we get  that  $h_i$ is equal to the number of top dimensional simplices which attach on $i$ facets to the union of previous simplices in a shelling order. %Evidently then, $$h(\C, \b)=\sum_{i=0}^d h_i \b^i,$$ with nonnegative coefficients.
\qed

\medskip

A nice example of the polynomial 
$h(\C, \b)$ is in the case when we let $\C$  be a unimodular triangulation of    $\F_{\widetilde{P_n}}$, where $P_n=([n], \{(i, i+1)| i \in [n-1]\})$. In this case the coefficients of $h(\C, \b)$ are given by the  Narayana numbers, which can be seen via the results \cite[Theorem 4.4]{groth} and  \cite[Exercise 6.31b]{ec2}.


\medskip

Using Theorem \ref{pos} we are ready to prove a special case of Kirillov's  \cite[Conjecture 2]{k2}.

\begin{conjecture} \cite[Conjecture 2]{k2} Let $k_1, \ldots, k_{n-1}$ be a sequence of nonnegative integers and let $M=x_{12}^{k_1}x_{23}^{k_2}\cdots x_{n-1, n}^{k_{n-1}}$. Then the reduced form of $M$    evaluated at $\x=(1, \ldots, 1)$ and $\b-1$  in  $\widetilde{ACYB_n}(\beta)$ is a polynomial in $\beta$ with nonnegative coefficients. 
\end{conjecture}


\begin{theorem} \label{special} \cite[cf. Conjecture 2]{k2}. The reduced form of $x_{12}x_{23}\cdots x_{n-1,n}$ evaluated at $\x=(1, \ldots, 1)$ and $\b-1$ in  $\widetilde{ACYB_n}(\beta)$  is a polynomial in $\b$ with nonnegative coefficients.
\end{theorem}

\proof  In \cite{m2} it is proved that the monomial $x_{12}x_{23}\cdots x_{n-1,n}$  can be reduced in $\widetilde{ACYB_n}(\beta)$ so that the resulting monomials in the reduced form have no variables of the form $x_{ij}x_{jk}$, $i<j<k$. Thus, reduced form of $x_{12}x_{23}\cdots x_{n-1,n}$ evaluated at $\x=(1, \ldots, 1)$ and $\b-1$ in  $\widetilde{ACYB_n}(\beta)$  is equal to the reduced form of $x_{12}x_{23}\cdots  x_{n-1,n}$ evaluated at $\x=(1, \ldots, 1)$ and $\b-1$ in  $\t$.  Therefore we can apply Theorem \ref{pos} to obtain this result.
\qed


\section{Reduced forms and Ehrhart series}
\label{sec:ehr}

In this section we connect the $h$-polynomials of triangulations of flow polytopes  to the  Ehrhart series of flow polytopes, and using Theorem \ref{thm-h} we tie this in with reduced forms in the subdivision algebra. As a corollary to our results, we generalize \cite[Theorem 3.10]{k2}. 


Recall that for a  polytope $\mathcal{P}\subset \mathbb{R}^{N}$, the {$t^{th}$ dilate} of $\mathcal{P}$ is $\displaystyle t \mathcal{P}=\{(tx_1, \ldots, tx_{N}) \mid  (x_1, \ldots, x_{N}) \in \mathcal{P}\}.$ The number of lattice points of $t\mathcal{P}$, where $t$ is a nonnegative integer and $\mathcal{P}$ is a convex polytope, is given by the {\bf Ehrhart function} $i({\mathcal{P}}, t)$. If $\mathcal{P}$ has integral vertices then $i({\mathcal{P}}, t)$ is a  polynomial.

The following is a well-known result specialized to  $\F_{\widetilde{G}}$.

\begin{lemma} \label{thm-ehr} Let  $\C$ be a unimodular triangulation of  $\F_{\widetilde{G}}$.
Then
\begin{equation}\label{h-ehrhart1} h(\C, \b)=\sum_{m\geq 0}(i(\F_{\widetilde{G}}, m)\b^m)(1-\b)^{\dim(\F_{\widetilde{G}})+1}.\end{equation}
\end{lemma}



\begin{corollary} \label{cor} We have 
\begin{equation}Q_G^{\t}(\b-1)=\sum_{m\geq 0}(\l(\F_{\widetilde{G}}, m)\b^m)(1-\b)^{\dim(\F_{\widetilde{G}})+1}.\end{equation} \end{corollary}

\proof Follows directly from Theorem \ref{thm-h} and Lemma  \ref{thm-ehr}.\qed

\begin{corollary}{\cite[Theorem 3.10]{k2}} 
\begin{equation}Q_{K_n}^{\t}(\b-1)=\sum_{m\geq 0}(\l(CRY_{n+1}, m)\b^m)(1-\b)^{{n+1 \choose 2}}.\end{equation} 
\end{corollary}

\proof The result follows from Corollary \ref{cor}  for $G=K_n$, since $\dim (\F_{\widetilde{K_n}})={{n+1 \choose 2}-1}$ and  $\l(CRY_{n+1}, m)=i(\F_{\widetilde{K_n}}, m)$, as explained in \cite{m-prod}. \qed


To state our final result, also a corollary of Corollary \ref{cor}, relating the reduced forms to Kostant partition functions, we remind the reader of the following definition.


 The {\bf Kostant partition function}  $K_G$ evaluated at the vector $\v \in \Z^{n+1}$ is defined as

\begin{equation} \label{kost} K_G(\v)= \#  \{ (b_{k})_{k \in [N]} \mid \sum_{k \in [N]} b_{k}  \a_k =\v \textrm{ and } b_{k} \in \Z_{\geq 0} \},\end{equation}


\noindent where $[N]=\{1,2,\ldots,N\}$ and  $\{\{\a_1, \ldots, \a_N\}\}$ is the multiset of vectors corresponding to the multiset of edges of $G$ under the correspondence which associates an edge  $(i, j)$, $i<j$, of $G$ with a positive type $A_n$ root $e_i-e_j$, where $e_i$ is the $i$th standard basis vector in $\mathbb{R}^{n+1}$.
In other words, $K_G(\v)$ is the number of ways to write the vector $\v$ as a $\mathbb{N}$-linear combination of the positive type $A_n$ roots (with possible multiplicities) corresponding to the edges of $G$, without regard to order. 
  


\begin{corollary} For any graph $G$ we have 
\begin{equation}Q_G^{\t}(\b-1)=\sum_{m\geq 0}(K_{\widetilde{G}}(m, 0, \ldots, 0, -m)\b^m)(1-\b)^{\#E(G)+\#V(G)},\end{equation}where $K_{\widetilde{G}}$ is the Kostant partition function for ${\widetilde{G}}$. \end{corollary}

\proof  Follows from Corollary \ref{cor}   since $\l(\F_{\widetilde{G}}, m)=K_{\widetilde{G}}(m, 0, \ldots, 0, -m)$ is a simple corollary of the definitions of these objects and $\dim(\F_{\widetilde{G}})=\#E(\widetilde{G})-\#V(\widetilde{G})+1=\#E(G)+\#V(G)-1.$ For  detailed explanations of both of these and related results see \cite{mm}. \qed






%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection*{Acknowledgements}
The author  thanks Federico Ardila, Louis Billera and Ed Swartz for several  interesting  discussions regarding this work. The author also thanks Alejandro H. Morales for many inspiring conversations about flow polytopes over the course of the years and the anonymous referee for their suggestions. 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \bibliographystyle{plain} 
% \bibliography{myBibFile} 
% If you use BibTeX to create a bibliography
% then copy and past the contents of your .bbl file into your .tex file

\begin{thebibliography}{99}

\bibitem{BV2}
{Welleda Baldoni and Michelle Vergne}. \newblock {K}ostant partitions functions and flow polytopes. \newblock
 {\em Transform. Groups},
no  {3-4},
{447--469},
 {2008}.

 
\bibitem{CRY}
{Clara S. Chan,   David P. Robbins and  David S. Yuen}.  \newblock  On the volume of a certain polytope. \newblock 
{\em Experiment. Math.},
no. {1},
 {91--99},
 {2000}.


\bibitem{kosh}
{Vladimir I.  Danilov,  Alexander V.  Karzanov  and Gleb A. Koshevoy}.  \newblock Coherent fans in the space of flows in framed graphs.  \newblock
{\em DMTSC proc., FPSAC 2012 Nagoya, Japan}, {483--494},
{2012}.


\bibitem{fk}
 {Sergey~Fomin and Anatol~N.~Kirillov}. \newblock Quadratic algebras, Dunkl elements, and Schubert calculus.
\newblock
{\em Advances in Geometry},
no. {172},
 {147--182},
 {1999}.
 



\bibitem{Kir} Anatol N. Kirillov.   \newblock {Ubiquity of {K}ostka polynomials}.  \newblock
 \arxiv{math/9912094},
1999.




\bibitem{k2}
 Anatol N. Kirillov.  \newblock On some combinatorial and algebraic properties of {D}unkl elements.
 \newblock
{\em RIMS preprint},
2012.



\bibitem{k2014}  Anatol N. Kirillov.  \newblock  On some quadratic algebras, {D}unkl elements, Schubert, Grothendieck, Tutte and reduced polynomials.
 \newblock
{\em RIMS preprint},
2014.



\bibitem{m2} Karola M\'esz\'aros. \newblock
{Root polytopes, triangulations, and the subdivision algebra, {I}}. \newblock
{\em Trans. Amer. Math. Soc.},
vol. 363,
no. {8},
{4359--4382},
 2011.

\bibitem{m1}
Karola M\'esz\'aros.  \newblock
{Root polytopes, triangulations, and the subdivision algebra, {I}{I}}.
 \newblock {\em Trans. Amer. Math. Soc.},
vol. {363},
no. {11},
{6111--6141},
 {2011}.




\bibitem{h-poly2} Karola  M\'esz\'aros.  \newblock {$h$-polynomials of  reduction trees}. \newblock \url{http://arxiv.org/abs/1407.2684},
{2014}.

\bibitem{m-prod}
Karola M\'esz\'aros.  \newblock
{Product formulas for volumes of flow polytopes}. \newblock
{\em Proc. Amer. Math. Soc.},  vol. 143, no. 3, 937--954, 2015. 

 
\bibitem{groth} Karola
M{\'es}z{\'a}ros. \newblock 
{Pipe dream complexes  and triangulations of  root polytopes belong together.}
 \newblock \arxiv{1502.03991}, {2015}


\bibitem{mm}
Karola  M\'esz\'aros and Alejandro H. Morales.  \newblock  Flow polytopes of signed graphs and the {K}ostant partition function.  \newblock {\em Int. Math. Res. Notices}  no. 3: 830--871, 2015.

\bibitem{p} Alexander
Postnikov.  \newblock
Personal communication,
2010.


\bibitem{schrijver}
{Alexander Schrijver}.  \newblock
{\em Combinatorial Optimization, Volume C.} \newblock Springer-Verlag Berlin Heidelberg, 2003.




\bibitem{Stcom} Richard P.  Stanley.
\newblock {\em Combinatorics and Commutative Algebra},
\newblock {Birkh\"auser}, 1996. 


\bibitem{ec2} {Richard P. Stanley}.  \newblock
   {\em Enumerative combinatorics. {V}ol. 2}, \newblock
{Cambridge Studies in Advanced Mathematics},
{no. 62},
{Cambridge University Press, Cambridge},
 {1999}.

\bibitem{S} Richard P.  Stanley. \newblock
 {Acyclic flow polytopes and {K}ostant's partition function}.
\newblock  Conference transparencies, \url{http://math.mit.edu/~rstan/trans.html},
 {2000}.



\bibitem{Z} Doron
Zeilberger.    \newblock {Proof of a conjecture of {C}han, {R}obbins, and {Y}uen.}  \newblock
{\em Electron. Trans. Numer. Anal.},
 {147--148},
{1999}.

\end{thebibliography}

\end{document}