%% if you are submitting an initial manuscript then you should have submission as an option here
%% if you are submitting a revised manuscript then you should have revision as an option here
%% otherwise options taken by the article class will be accepted
\documentclass[submission]{FPSAC2019}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

\articlenumber{13}
\addbibresource{13.bib}

%% note that the class file already loads {amsmath, amsthm, amssymb}

%\newtheorem{thm}{Theorem}
%\newtheorem{lem}{Lemma}

\newcommand{\vanish}[1]{}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{notation}[theorem]{Notation}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{example}[theorem]{Example}
\newtheorem{remark}[theorem]{Remark}

\numberwithin{equation}{section}

\newcommand{\SSSS}{{\mathfrak S}}

\newcommand{\Ppp}{{\mathbb P}}
\newcommand{\Rrr}{{\mathbb R}}
\newcommand{\Zzz}{{\mathbb Z}}
\newcommand{\Ddd}{{\widetilde{D}}}

\newcommand{\Simplex}{\Delta}

\newcommand{\rest}[2] {\left.#1\right| {_{#2}}} 

\DeclareMathOperator{\conv}{conv}
\DeclareMathOperator{\DP}{DP}
\DeclareMathOperator{\SP}{SP}
\DeclareMathOperator{\Head}{Head}
\DeclareMathOperator{\Tail}{Tail}
\DeclareMathOperator{\tw}{tw}


\usepackage{lipsum}
\usepackage{color}
\usepackage{tikz-dependency}
\usepackage{tikz}
\usepackage{enumerate}



%% define your title in the usual way
\title[Uniform triangulations]{Refined face count in uniform
  triangulations of the Legendre polytope}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{{Richard
  Ehrenborg\thanks{\href{richard.ehrenborg@uky.edu}{richard.ehrenborg@uky.edu}. Richard
    Ehrenborg was partially supported by Grant \#429370 of the Simons
    Foundation.}\addressmark{1}, G\'abor
  Hetyei\thanks{\href{ghetyei@uncc.edu}{ghetyei@uncc.edu} G\'abor Hetyei
    was partially supported by Grant  \#514648 of the Simons
    Foundation.}\addressmark{2}, \and
  Margaret
  Readdy\thanks{\href{margaret.readdy@uky.edu}{margaret.readdy@uky.edu}.
  Margaret Readdy was partially supported by Grant  \#422467 of the Simons
    Foundation.}\addressmark{1}}} 

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Department of Mathematics, University of
  Kentucky, Lexington, KY 40506-0027\\ \addressmark{2}Department of Mathematics and Statistics,
  UNC-Charlotte, Charlotte NC 28223-0001}

%% put the date of submission here
\received{\today}

%% leave this blank until submitting a revised version
%\revised{}

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\abstract{The Legendre polytope is the convex hull of all pairwise differences of
the basis vectors,
also known as the full root polytope of type~$A$.
We describe all flag triangulations of this polytope
that are uniform in the sense that the edges may be described as a
function of the relative order of the indices of the four basis vectors
involved. We also determine the refined face counts of these
triangulations that keeps track of 
the number of forward and backward arrows in each face.}

\resumetitle{R\'esum\'e}
%% put your French abstract here, or comment this out if you don't have one
\resume{Le polytope de Legendre, aussi connu sous le nom polytope
  de racine pleine de type $A$,  est l'enveloppe convexe des
  diff\'erences par paire des vecteurs de base. Nous d\'ecrivons toutes
  les triangulations drapeau de ce polytope qui sont uniformes dans le
  sens que les ar\^etes ne dependent que de l'ordre relative des quatres
  vecteurs de base impliqu\'es. Nous d\'eterminons aussi le compte
  raffin\'e de faces qui fait suivi le nombre des ar\^etes vers l'avant
  et ceux en arri\`ere dans chaque face.}

%% put your keywords here, or comment this out if you don't have them yet
%\keywords{}

%% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier
%% regardless of how you do it, please use numerical citations, ie. [xx, yy] in the text

%% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex
%% but you can use bibtex if you want
%\usepackage[backend=bibtex]{biblatex}
%\addbibresource{sample.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands
%\addbibresource{biblio.bib}

\makeatletter
\def\blfootnote{\xdef\@thefnmark{}\@footnotetext}
\makeatother

\begin{document}

\maketitle
%% note that you DO NOT have to put your abstract here -- it is generated by \maketitle and the \abstract and \resume commands above

\section{Introduction}

\blfootnote{A full length version
    of this manuscript may be found at \url{https://math.uncc.edu/sites/math.uncc.edu/files/fields/preprint_archive/paper/2018_09.pdf}}

Triangulations of root polytopes and of products of simplices have been a
subject of intense study in recent
years~\cite{Ardila_Beck_Hosten_Pfeifle_Seashore,Ceballos_Padrol_Sarmiento_old,
  Ceballos_Padrol_Sarmiento, Cellini_Marietti_abelian,
  Gelfand_Graev_Postnikov}. 
Motivated by an observation made
in~\cite{Cori_Hetyei}, the authors recently~\cite{Ehrenborg_Hetyei_Readdy} 
established that the Simion type~$B$ associahedron~\cite{Simion} may be
realized as a pulling triangulation of the Legendre polytope, defined as
the convex hull of all differences of pairs of basis vectors in
Euclidean space. These vertices can be thought of as {\em arrows} between
numbered nodes. They also showed that all pulling triangulations are
flag. The Legendre polytope is the centrally symmetric variant of the
type~$A$ root polytope whose triangulations were studied by Gelfand, Graev and
Postnikov~\cite{Gelfand_Graev_Postnikov}. A question naturally arises:
Are there other reasonably uniform triangulations of the Legendre
polytope?

In this work we fully answer this question. We consider flag
triangulations that are uniform in the sense that the flag condition
depends only on the relative order on the numbering of the basis vectors
involved, and classify all such triangulations. The key tool we use is a
characterization of triangulations of a product of simplices by
Oh and Yoo~\cite{Oh_Yoo_2} in terms of {\em matching
  ensembles}. We determine that there are three classes of triangulations:
variants of the lexicographic pulling triangulation, variants of the
revlex pulling triangulation, and variants of the triangulation
representing the Simion type~$B$ associahedron. 
All triangulations of the boundary of the Legendre
polytope have the same face numbers.

To distinguish between the three
major classes, we introduce a refined face count which keeps track of
the number of forward and backward arrows in each face. Remarkably we
find the refined face count in a 
triangulation belonging to the lexicographic class yields the same face
numbers for a fixed dimension, regardless how we fix the number of
forward and backward arrows. The variants of the Simion type~$B$
associahedron all have the same refined face numbers, up to exchanging
the forward and backward arrows. Finally, the refined face count for the
revlex triangulation and its variants leads to considering an exponential
generating function whose second partial derivative may be expressed in
terms of modified Bessel functions. Weighted generalizations of the
Delannoy numbers play a crucial role in the refined face count in the
revlex and Simion class, whereas the Catalan numbers play a key role in the
refined face count in the lex and the Simion class.   

\section{Preliminaries}
\label{section_preliminaries}

The {\em Legendre polytope}~$P_{n}$~\cite{Hetyei_Legendre}
is the convex hull of the $n(n+1)$ vertices $e_{j}-e_{i}$ where $i \neq j$
and
$\{e_{1}, e_{2}, \ldots, e_{n+1}\}$
is the orthonormal basis of the Euclidean space $\mathbb{R}^{n+1}$.
It was first studied by Cho~\cite{Cho}, and it is called the
``full'' type~$A$ root polytope in the work of
Ardila, Beck, Ho\c{s}ten, Pfeifle and
Seashore~\cite{Ardila_Beck_Hosten_Pfeifle_Seashore}. 
%The name Legendre polytope~\cite{Hetyei_Legendre} is motivated by the
%fact that the polynomial
%$\sum_{j=0}^{n} f_{j-1} \cdot ((x-1)/2)^{j}$
%is the $n$th Legendre polynomial, where $f_{i}$ is the number of
%$i$-dimensional faces in any pulling triangulation of the boundary of~$P_{n}$.
%Another way to view the Legendre polytope is to
%intersect the hyperplane
%$x_{1} + x_{2} + \cdots + x_{n+1} = 0$
%with the $(n+1)$-dimensional cross-polytope
%formed by the convex hull of the vertices
%$\pm 2e_{1}$, $\pm 2e_{2}$, $\ldots$, $\pm 2 e_{n+1}$.
%The Legendre polytope $P_{n}$
It contains the root polytope $P_{n}^{+}$, defined
as the convex hull of the origin and the set of points $e_{j}-e_{i}$,
where $i<j$, first studied by Gelfand, Graev and
Postnikov~\cite{Gelfand_Graev_Postnikov} and later by
Postnikov~\cite{Postnikov_P}.
%Many properties of the Legendre polytope $P_{n}$
%are straightforward generalizations of the properties of the root
%polytope $P_{n}^{+}$.  

We use the shorthand notation $(i,j)$
for the vertex $e_{j}-e_{i}$
%of the Legendre polytope~$P_{n}$.
We may think of these vertices as the set of all
directed nonloop edges on the vertex set $\{1,2, \ldots, n+1\}$. To avoid
confusion between edges and vertices of the Legendre polytope, we will
refer to the vertices of~$P_{n}$ as {\em arrows}, and we will use the
notation $V_{n}=\{(i,j) \:\: : \:\: 1 \leq i,j \leq n+1, i \neq j\}$. 
%The root polytope
%$P_{n}^{+}$ is then the convex hull of the origin and of the forward
%arrows. Suppressing the orientation we arrive at the edges
%representing vertices in the work of Gelfand, Graev and
%Postnikov~\cite{Gelfand_Graev_Postnikov}. 

A subset of arrows is contained in some face of $P_{n}$
exactly when there is no $i \in \{1,2, \ldots, n+1\}$ that is both the
head and the tail of an arrow;
see~\cite[Lemmas~4.2 and~4.4]{Hetyei_Legendre}.
Equivalently, the faces are products of two
simplices~\cite[Lemma 2.2]{Ehrenborg_Hetyei_Readdy}: we may write them
as $\Simplex_{I} \times \Simplex_{J}$ where $I,J\neq \emptyset$, $I\cap
J=\emptyset$ and $\Simplex_{K}$
denotes the convex hull of the set $\{e_{i} \: : \: i \in K\}$ for
$K\subseteq \{1,2, \ldots,  n+1\}$.
%The analogous observations regarding the faces of the root polytope
%$P_{n}^{+}$ that do not contain the origin may be found
%in~\cite{Gelfand_Graev_Postnikov} where the sets of edges
%(forward arrows in our terminology) representing vertices contained in a
%proper face are called {\em admissible}.
%Facets of $P_{n}$ are exactly the faces 
%$\Simplex_{I} \times \Simplex_{J}$ where the disjoint union of $I$ and $J$
%is $\{1,2, \ldots, n+1\}$. 
%The edges of $P_{n}$ are of the form
%$\Simplex_{I} \times \Simplex_{J}$ where $\{|I|,|J|\}=\{1,2\}$. 
%The two-dimensional faces 
%$\Simplex_{I} \times \Simplex_{J}$
%of $P_{n}$ are either squares when $|I| = |J| = 2$ or
%triangles when $\{|I|,|J|\}=\{1,3\}$. 
Affine independent subsets of vertices of faces of the Legendre
polytope are described as follows.
A set $S=\{(i_{1},j_{1}),(i_{2},j_{2}), \ldots, (i_{k},j_{k})\}$
is a $(k-1)$-dimensional simplex if and only if, 
disregarding the orientation of the directed
edges, the set $S$ contains no cycle, that is, it is a
forest~\cite[Lemma~2.4]{Hetyei_Legendre}. The analogous observations were
made for the root polytope $P^{+}_{n}$ in~\cite{Gelfand_Graev_Postnikov}
and for products of simplices
in~\cite[Lemma~6.2.8]{deLoera_Rambau_Santos}
(see also~\cite[Lemma~2.1]{Ceballos_Padrol_Sarmiento_old}).     

In a recent paper~\cite{Ehrenborg_Hetyei_Readdy}, the authors
have shown that the Simion type~$B$ associahedron~\cite{Simion} is
combinatorially equivalent to a pulling triangulation of the boundary of
the Legendre polytope. For an exact definition of a pulling
triangulation we refer the reader
to~\cite{Ehrenborg_Hetyei_Readdy}. Here we only recall the following key
observation~\cite[Theorem 3.1]{Ehrenborg_Hetyei_Readdy}: every pulling
triangulation of the boundary of the Legendre polytope $P_{n}$ is {\em
  flag}, that is, a subset of vertices is a face exactly when each pair of
vertices in the subset is an edge. Thus the triangulation giving rise
to a combinatorial equivalent of the Simion type~$B$ associahedron is
completely determined by the rules given in the associated column of
\cref{table_six_way}. 

\newcommand{\lift}[1]{\raisebox{2.5mm}{#1}}

\newcommand{\base}[4]
{
\node[circle, inner sep = 0.9pt] (a1) at (0, 0) {$#1$};
\node[circle, inner sep = 0.9pt] (a2) at (0.7, 0) {$#2$};
\node[circle, inner sep = 0.9pt] (a3) at (1.4, 0) {$#3$};
\node[circle, inner sep = 0.9pt] (a4) at (2.1, 0) {$#4$};
}

\newcommand{\TheNewNewTable}{
\begin{table}[t]
\centering
\begin{tabular}{|c|c||c|c|c|}  
\hline
  Type & Order of nodes & Type~$B$ & Lexicographic & Revlex \\
  & & associahedron & pulling & pulling \\
\hline
\hline  
\lift{$THTH$} & 
\lift{$i_{1}<j_{1}<i_{2}<j_{2}$}
& 
\begin{tikzpicture}
\base{i_{1}}{j_{1}}{i_{2}}{j_{2}}
\draw[->, thick] (a1) to[out=55, in=125] (a4);
\draw[<-, thick] (a2) to[out=55, in=125] (a3);
\end{tikzpicture}
&
\begin{tikzpicture}
\base{i_{1}}{j_{1}}{i_{2}}{j_{2}}
\draw[->, thick] (a1) to[out=55, in=125] (a2);
\draw[->, thick] (a3) to[out=55, in=125] (a4);
\end{tikzpicture}
&
\begin{tikzpicture}
\base{i_{1}}{j_{1}}{i_{2}}{j_{2}}
\draw[->, thick] (a1) to[out=55, in=125] (a4);
\draw[<-, thick] (a2) to[out=55, in=125] (a3);
\end{tikzpicture}
\\
\hline
\lift{$HTHT$} & 
\lift{$j_{1}<i_{1}<j_{2}<i_{2}$}
& 
\begin{tikzpicture}
\base{j_{1}}{i_{1}}{j_{2}}{i_{2}}
\draw[<-, thick] (a1) to[out=55, in=125] (a2);
\draw[<-, thick] (a3) to[out=55, in=125] (a4);
\end{tikzpicture}
&
\begin{tikzpicture}
\base{j_{1}}{i_{1}}{j_{2}}{i_{2}}
\draw[<-, thick] (a1) to[out=55, in=125] (a2);
\draw[<-, thick] (a3) to[out=55, in=125] (a4);
\end{tikzpicture}
&
\begin{tikzpicture}
\base{j_{1}}{i_{1}}{j_{2}}{i_{2}}
\draw[<-, thick] (a1) to[out=55, in=125] (a4);
\draw[->, thick] (a2) to[out=55, in=125] (a3);
\end{tikzpicture}
\\
\hline
\lift{$THHT$} & 
\lift{$i_{1}<j_{1}<j_{2}<i_{2}$}
& 
\begin{tikzpicture}
\base{i_{1}}{j_{1}}{j_{2}}{i_{2}}
\draw[->, thick] (a1) to[out=55, in=125] (a2);
\draw[<-, thick] (a3) to[out=55, in=125] (a4);
\end{tikzpicture}
&
\begin{tikzpicture}
\base{i_{1}}{j_{1}}{j_{2}}{i_{2}}
\draw[->, thick] (a1) to[out=55, in=125] (a2);
\draw[<-, thick] (a3) to[out=55, in=125] (a4);
\end{tikzpicture}
&
\begin{tikzpicture}
\base{i_{1}}{j_{1}}{j_{2}}{i_{2}}
\draw[->, thick] (a1) to[out=55, in=125] (a3);
\draw[<-, thick] (a2) to[out=55, in=125] (a4);
\end{tikzpicture}
\\
\hline
\lift{$HTTH$} & 
\lift{$j_{1}<i_{1}<i_{2}<j_{2}$}
& 
\begin{tikzpicture}
\base{j_{1}}{i_{1}}{i_{2}}{j_{2}}
\draw[<-, thick] (a1) to[out=55, in=125] (a2);
\draw[->, thick] (a3) to[out=55, in=125] (a4);
\end{tikzpicture}
&
\begin{tikzpicture}
\base{j_{1}}{i_{1}}{i_{2}}{j_{2}}
\draw[<-, thick] (a1) to[out=55, in=125] (a2);
\draw[->, thick] (a3) to[out=55, in=125] (a4);
\end{tikzpicture}
&
\begin{tikzpicture}
\base{j_{1}}{i_{1}}{i_{2}}{j_{2}}
\draw[<-, thick] (a1) to[out=55, in=125] (a3);
\draw[->, thick] (a2) to[out=55, in=125] (a4);
\end{tikzpicture}
\\
\hline
\lift{$TTHH$} &  
\lift{$i_{1}<i_{2}<j_{1}<j_{2}$}
&  
\begin{tikzpicture}
\base{i_{1}}{i_{2}}{j_{1}}{j_{2}}
\draw[->, thick] (a1) to[out=55, in=125] (a4);
\draw[->, thick] (a2) to[out=55, in=125] (a3);
\end{tikzpicture}
&
\begin{tikzpicture}
\base{i_{1}}{i_{2}}{j_{1}}{j_{2}}
\draw[->, thick] (a1) to[out=55, in=125] (a3);
\draw[->, thick] (a2) to[out=55, in=125] (a4);
\end{tikzpicture}
&
\begin{tikzpicture}
\base{i_{1}}{i_{2}}{j_{1}}{j_{2}}
\draw[->, thick] (a1) to[out=55, in=125] (a4);
\draw[->, thick] (a2) to[out=55, in=125] (a3);
\end{tikzpicture}
\\
\hline
\lift{$HHTT$} & 
\lift{$j_{1}<j_{2}<i_{1}<i_{2}$}
& 
\begin{tikzpicture}
\base{j_{1}}{j_{2}}{i_{1}}{i_{2}}
\draw[<-, thick] (a1) to[out=55, in=125] (a4);
\draw[<-, thick] (a2) to[out=55, in=125] (a3);
\end{tikzpicture}
&
\begin{tikzpicture}
\base{j_{1}}{j_{2}}{i_{1}}{i_{2}}
\draw[<-, thick] (a1) to[out=55, in=125] (a3);
\draw[<-, thick] (a2) to[out=55, in=125] (a4);
\end{tikzpicture}
&
\begin{tikzpicture}
\base{j_{1}}{j_{2}}{i_{1}}{i_{2}}
\draw[<-, thick] (a1) to[out=55, in=125] (a4);
\draw[<-, thick] (a2) to[out=55, in=125] (a3);
\end{tikzpicture}
\\
\hline
\end{tabular}
\vspace*{3mm}
\caption{Pairs of arrows that are edges in three triangulations of
the boundary~$\partial P_{n}$ of the Legendre polytope.}
\label{table_six_way}  
\end{table}
}

\TheNewNewTable



The last two columns in \cref{table_six_way} are the analogous
rules for two other pulling triangulations of the boundary of the
Legendre polytope $P_{n}$, also discussed
in~\cite{Ehrenborg_Hetyei_Readdy}. These are the lexicographic (lex) and
revlex pulling orders, introduced
in~\cite{Hetyei_Legendre}. Their restriction to the root
polytope $P^{+}_n$ are called the antistandard, respectively standard
triangulations in~\cite{Gelfand_Graev_Postnikov}. 
The reader may take
\cref{table_six_way} as a definition of these flag complexes.

\section{Classifying uniform flag triangulations of the Legendre polytope}
\label{section_classification}

A common property of all three flag complexes described in
\cref{table_six_way} is that the edges are defined in
a {\em uniform fashion}:
\begin{definition}
\label{definition_uflag}
A flag simplicial complex $\triangle_{n}$ on the vertex set~$V_{n}$
is a {\em uniform flag complex}
if determining whether or not
a pair of vertices $\{(i_{1},j_{1}),(i_{2},j_{2})\}$ forms an edge
depends only on the equalities and inequalities
between the values of $i_{1}$, $i_{2}$, $j_{1}$ and~$j_{2}$.
\end{definition}  

%We begin with the necessary conditions for describing
%uniform flag triangulations.
To facilitate making statements,
we introduce some new terminology and notation. We use the letter
$T$ to mark the tail of each arrow and the letter $H$ to mark the head.
For each pair of arrows on four nodes, we will indicate the
relative order of the two heads and two tails by writing down the
appropriate letters left to right in the order as they occur. We will
refer to the resulting word as the {\em type} of the pair of arrows.
After that we will simply state in words the condition
that a pair of arrows
of a given type must satisfy to be an edge of the triangulation.
Three examples of this convention are given in \cref{table_six_way}.
Our main classification result is the following.
\begin{theorem}
Let  $\triangle_{n}$ be a uniform flag complex on the vertex set~$V_{n}$ for
some $n \geq 5$ that satisfies the necessary conditions stated in
\cref{proposition_easy} below.
Then the complex~$\triangle_{n}$ represents a triangulation of
the boundary~$\partial P_{n}$ of the Legendre polytope if and only if it
satisfies exactly one of the following conditions:
\begin{enumerate}
\item
Both $THTH$ and $HTHT$ types of pairs of arrows do not nest,
and both $HTTH$ and $THHT$ types of arrows do not cross. Uniform flag 
triangulations induced by the lexicographic pulling order belong to this
class, hence we call it {\em the lex class}.
\item
Both $THTH$ and $HTHT$ types of pairs of arrows nest,
and both $HTTH$ and $THHT$ types of arrows cross. Uniform flag 
triangulations induced by the revlex pulling order belong to this
class, hence we call it {\em the revlex class}.
\item
Exactly one of the $THTH$ and $HTHT$ types of pairs of arrows nest.
Furthermore, if
both $THHT$ and $HTTH$ types of pairs cross
then both $TTHH$ and $HHTT$ types of pairs nest.  The Simion type~$B$
associahedron belongs to this class, 
and hence we call it  {\em the Simion class}.
\end{enumerate}
\label{theorem_main}
\end{theorem}
The necessity part of \cref{theorem_main} depends on a few
technical propositions and the following geometric observation.
\begin{proposition}
\label{proposition_easy}
Let $\triangle_{n}$ be a uniform flag complex on the vertex set~$V_{n}$.
Identify each vertex  $(i,j) \in V_{n}$
with the vertex $e_{j} - e_{i}$ of the Legendre polytope~$P_{n}$.
If the complex $\triangle_{n}$ represents
a triangulation of the boundary~$\partial P_{n}$
of the Legendre polytope then it satisfies the following criteria:  
\begin{enumerate}
\item
There is no edge of the form $\{(i,j),(j,k)\}$ in the complex~$\triangle_{n}$.
\item
For each three-element subset $\{i,j,k\}$ of $\{1,2, \ldots, n+1\}$,
the two sets $\{(i,j),(i,k)\}$ and $\{(j,i),(k,i)\}$ are edges
in the complex~$\triangle_{n}$.
\item
For each four-element subset $\{i_{1},i_{2},j_{1},j_{2}\}$ of
$\{1,2, \ldots, n+1\}$, exactly one of the two sets $\{(i_{1},j_{1}),(i_{2},j_{2})\}$
and $\{(i_{1},j_{2}),(i_{2},j_{1})\}$ is an edge
in the complex~$\triangle_{n}$.
\end{enumerate}  
\end{proposition}
The key tool in verifying sufficiency is the
following result. 
\begin{theorem}
Let $\triangle_{n}$ be a uniform flag complex on the vertex set~$V_{n}$
satisfying the conditions
of \cref{proposition_easy}. Let $\mathcal{M}$ be the family of all
faces that are matchings, that is, set
$$
\mathcal{M}
=
\{\{(i_{1},j_{1}),(i_{2},j_{2}), \ldots, (i_{k},j_{k})\} \in \triangle_{n}
\: : \: 
|\{i_{1},j_{1},i_{2},j_{2}, \ldots, i_{k},j_{k}\}|=2k\}.
$$
Identify each vertex $(i,j)$ with the vertex $e_{j} - e_{i}$ of the
Legendre polytope.
Then the complex $\triangle_{n}$ represents a triangulation of
the boundary~$\partial P_{n}$ of the Legendre polytope if and only if 
the family of matchings $\mathcal{M}$ satisfies the following two properties:   
\begin{itemize}
\item[(SA)]
For each $I,J\subset \{1,2, \ldots,  n+1\}$ satisfying $I\cap J = \emptyset$ and $|I|=|J|$
there is a unique $\sigma\in {\mathcal{M}}$ such that 
$\sigma\subseteq I\times J$ and $|\sigma|=|I|$;
\item[(LA)]
Assume $I,J \subset \{1,2, \ldots,  n+1\}$ satisfies $I \cap J = \emptyset$
and let $\sigma$ be a non-empty matching in $\mathcal{M}$ such that
$\sigma\subseteq I\times J$.
Then for each $k \not \in I \cup J$ there is
an edge $(i,j) \in \sigma$ such that
$(\sigma-\{(i,j)\}) \cup \{(k,j)\} \in {\mathcal{M}}$.
Also, for each $k \not \in I \cup J$ there is
an edge $(i,j) \in \sigma$ such that
$(\sigma-\{(i,j)\}) \cup \{(i,k)\}\in {\mathcal{M}}$. 
\end{itemize}
\label{theorem_legendreme}  
\end{theorem}  
The proof of \cref{theorem_legendreme} relies on a nontrivial
revamping of the characterization of triangulations of a product of two
simplices given by S.\ Oh and H.\ Yoo~\cite{Oh_Yoo_2}.
See also~\cite{Ceballos_Padrol_Sarmiento_old} and
\cite[Lemma~2.5]{Ceballos_Padrol_Sarmiento}.  In the proof at some
point we use a slight generalization
of~\cite[Lemma~12.6]{Postnikov_P}. The labels (SA) and (LA) refer to the
terms {\em support axiom} and {\em linkage axiom} used by  S.\ Oh and
H.\ Yoo. They also introduce a {\em closure axiom} which is
trivially verified in our setting.



\section{Tools for refined face enumeration}
\label{section_tools}

In this section we list a few tools we repeatedly used to prove our
enumerative results. 
Uniform triangulations of $\partial P_{n}$ are defined by a set of six rules, 
independent of the dimension. For a fixed set of rules, we will
simultaneously consider each triangulation $\triangle_{n}$ 
determined on the vertex set $V_{n}$ defined by these rules, for each~$n
\geq 0$. Note that $V_{0}=\emptyset$.
Let $\mathcal{F}  = (\mathcal{F}_{0}, \mathcal{F}_{1}, \ldots)$
be a sequence of collections of arrows, where
$\mathcal{F}_{n}$ is a family of subsets of $V_{n}$.
We define the associated generating function
$$
F(\mathcal{F}, x,y,t)
=
\sum_{n,i,j \geq 0} f(\mathcal{F}_{n},i,j) \cdot x^{i}y^{j}t^{n}
$$
where $f(\mathcal{F}_{n},i,j)$ is the number of sets in $\mathcal{F}_{n}$
consisting of $i$ forward arrows and $j$ backward arrows.
Our interest is to compute  this generating function
when $\mathcal{F}$ is the collection $(\triangle_{0},\triangle_{1},\ldots)$.
The number of cases to be considered can be reduced by extending the
notion of the {\em dual} and {\em reflected dual} triangulations to all
families:
\begin{lemma}
Let $\mathcal{F}  = (\mathcal{F}_{0}, \mathcal{F}_{1}, \ldots)$
be a sequence of collections of arrows, where $\mathcal{F}_{n} \subseteq
2^{V_{n}}$. Let $\mathcal{F}^{*}  = (\mathcal{F}_{0}^{*},
\mathcal{F}_{1}^{*}, \ldots)$ be the {\em dual family}, obtained by
reversing all arrows in all sets, and let $\overline{\mathcal{F}}  =
(\overline{\mathcal{F}_{0}}, 
\overline{\mathcal{F}_{1}}, \ldots)$ be the {\em reflected dual family},
obtained by reversing each arrow, and replacing each node $i$ in $V_{n}$
with $n+2-i$. Then we have 
$$
F(\mathcal{F}^{*}, x,y,t)
=
F(\mathcal{F}, y,x,t)
\quad\mbox{and}\quad
F(\overline{\mathcal{F}}, x,y,t)
=
F(\mathcal{F}, x,y,t).
$$
\label{lemma_dual_enumeration}  
\end{lemma}  
The families of uniform flag triangulations defined by a set of rules are {\em
coherent}  in the sense that they are closed under the insertion and
removal of isolated nodes. To make this informal observation precise,
consider the map $\pi_{k}: ({\mathbb N}-\{k\})\rightarrow {\mathbb N}$ given
by $\pi_{k}(m)=m$ for $m< k$ and  $\pi_{k}(m)=m-1$ for $m>k$.
\begin{definition}
Let $\mathcal{F} = (\mathcal{F}_{0}, \mathcal{F}_{1},\ldots)$
be a collection of families of sets such that for each~$n$
the family~$\mathcal{F}_{n}$ consists of subsets of $V_{n}$.
We call such a collection {\em coherent}
if for each subset $\sigma$ of $V_{n}$ and each
$k \in \{1,2, \ldots, n+1\}$ that is not incident to any arrow in $\sigma$, the
set $\pi_{k}(\sigma)=\{(\pi_{k}(i),\pi_{k}(j))\::\:   (i,j)\in \sigma\}$
belongs to $\mathcal{F}_{n-1}$ if and only if $\sigma$ belongs to
$\mathcal{F}_{n}$.  
In particular, for a coherent collection
$\mathcal{F}=(\mathcal{F}_{0}, \mathcal{F}_{1}, \ldots)$,
the empty set either belongs to all
$\mathcal{F}_{n}$ or it belongs to none of them. 
\end{definition}
By abuse of terminology we will say that $\mathcal F$ {\em contains the
  empty set} if all families $\mathcal{F}_{n}$ in it contain it. 
Sets of arrows in coherent collections may be enumerated by counting only
the {\em saturated}  sets in the families, which we now define. 
\begin{definition}
For $n\geq 1$, a subset $\sigma$ of $V_{n}$ is {\em saturated} if the set of
endpoints of its arrows is the set $\{1,2, \ldots, n+1\}$. We also
consider the empty set to be a saturated subset of $V_{0}=\emptyset$.
Given a coherent collection
$\mathcal{F} = (\mathcal{F}_{0}, \mathcal{F}_{1}, \ldots)$,
we denote the family of saturated sets in
$\mathcal{F}_{n}$ by~$\widehat{\mathcal{F}}_{n}$. 
\end{definition}

Note that $\widehat{\mathcal{F}_{0}}=\{\emptyset\}$ exactly when $\mathcal
F$ contains the empty set.
One of our key counting tools is the following observation.

\begin{lemma}
\label{lemma_all_full}
Given a coherent collection of families $\mathcal{F}$ of arrows, the
face generating function satisfies
\begin{align}
F(\mathcal{F},x,y,t)
& =
-
\frac{t}{(1-t)^{2}} \cdot \delta_{\mathcal{F}_{0}, \{\emptyset\}} 
+
\frac{1}{(1-t)^{2}} \cdot F\left(\widehat{\mathcal{F}},x,y,\frac{t}{1-t}\right) ,
\label{equation_all_full_1} \\
F(\widehat{\mathcal{F}},x,y,z)
& =
\frac{z}{1+z} \cdot \delta_{\widehat{\mathcal{F}}_{0}, \{\emptyset\}}
+
\frac{1}{(1+z)^{2}} \cdot F\left(\mathcal{F},x,y,\frac{z}{1+z}\right) ,
\label{equation_all_full_2}
\end{align}  
where $\delta$ denotes the Kronecker delta function.   
\end{lemma}  
Using \cref{lemma_all_full} it is always possible, albeit sometimes
tedious, to compute the generating function of all faces. An interesting
special case is counting all facets with a given number of forward and
backward arrows. The following statement is straightforward.
\begin{lemma}
\label{lemma_facets}
Let $\triangle_{n}$ be a uniform flag triangulation of the boundary $\partial
P_{n}$ of the Legendre polytope. Then a face $\sigma\in \triangle_{n}$ is a
facet if and only if it is saturated and contains no isolated nodes,
that is, every $i\in \{1,2,\ldots,n+1\}$ is incident to some element of
$\sigma$. 
\end{lemma}
In other words, as a subset of $V_{n}$, a facet is the set of edges of a
forest with no isolated nodes. Such a forest has $n+1$ nodes and $n$
arrows. If the number of forward arrows is $i$ then the number of
backward arrows is $n-i$ in such a forest, contributing a term
$x^iy^{n-i}t^n$ to the generating function of all faces and the term
$x^iy^{n-i}z^n$ to generating function of all saturated faces. 
\begin{corollary}
\label{corollary_facets}
Let $\mathcal{F}  =  (\triangle_{0}, \triangle_{1}, \ldots)$ be a
coherent family of uniform flag triangulations. Then the facet generating
function $\sum_{n\geq 0}\sum_{i=0}^n f(\triangle_{n},i,n-i)
x^iy^{n-i} z^n$ may be obtained by substituting $x/w$ into $x$, $y/w$ into~$y$
and $wz$ into $t$ in $F(\mathcal{F},x,y,t)$ and then evaluating the
resulting expression at $w=0$. Alternatively it may also be obtained by   
substituting $x/w$ into $x$, $y/w$ into~$y$
and $wz$ into $z$ in $F(\widehat{\mathcal{F}},x,y,z)$ and then evaluating the
resulting expression at $w=0$.  
\end{corollary}



For any uniform flag triangulation of the boundary $\partial P_{n}$ of the
Legendre polytope, the vertex sets consisting only of forward (backward)
arrows form subcomplexes whose face numbers are easier to count. We
first review the rephrasing of a known result. 

A useful way to express our results is in terms of
the generating function for the Catalan numbers:
\begin{align*}
C(u)
& =
\sum_{n \geq 0} C_{n} \cdot u^{n} = \frac{1-\sqrt{1-4u}}{2u} .
\end{align*}

\begin{proposition}
Let $\mathcal{F}$ be a family of uniform flag triangulations defined by a
set of rules that contains the rule that $HTHT$ types of pairs of arrows
do not nest. Then the following two identities hold:
\begin{align}
F(\mathcal{F},0,y,t)
& =
\frac{1-t-\sqrt{1-(4y+2)t+t^{2}}}{2yt} ,
\label{equation_F_0_y_t} \\
F(\widehat{\mathcal{F}},0,y,z)
& =
\frac{1}{1+z}\cdot \left(C(yz(z+1))+z\right) .
\label{equation_follow_full}  
\end{align}
\label{proposition_follow}  
\end{proposition}
  



%We will later use the following corollary of
%Proposition~\ref{proposition_follow}.
%It has a direct bijective proof;
%see~\cite{Ehrenborg_Hetyei_Readdy_Catalan}.
\begin{corollary}
Let $\mathcal{F}$ be a family of uniform flag triangulations  
such that $HTHT$ types of pairs of arrows do not nest.
Then the sum over all forests $F$ consisting of $k \geq 1$
backward arrows, no forward arrows and no isolated nodes is
\begin{align}
G_{k}(z) 
= 
\sum_{F} z^{\text{\#nodes of $F$}}
& = 
C_{k} \cdot z^{k+1} \cdot (z+1)^{k-1} .
\label{equation_G_1}
\end{align}
Similarly, if the uniform flag triangulations $\mathcal{F}$ 
satisfies the requirement that $THTH$ types of pairs of arrows do not nest,
then the sum over all forests $F$ consisting of $k \geq 1$
forward arrows, no backward arrows and no isolated nodes
also yields
the identity~\eqref{equation_G_1}.
\label{corollary_Catalan_times_1+z}
\end{corollary}
We will also use the following refined variant of
\cref{proposition_follow}.
\begin{proposition}
Let $\mathcal{F}$ be a family of uniform flag triangulations defined by a
set of rules that contains the rule that $HTHT$ type of pairs of arrows
do not nest. For each $n\geq 0$, let $\mathcal{F}^{(i)}_{n}$ denote the
set of all faces
where the sequence of heads and tails, listed in increasing order,
satisfies the condition that
the $i$ smallest nodes are heads and the next node is a tail.
Then the two resulting collections
$\mathcal{F}^{(i)}
= 
\bigl(\mathcal{F}^{(i)}_{0}, \mathcal{F}^{(i)}_{1}, \ldots\bigr)$
and
$\widehat{\mathcal{F}^{(i)}} =
\bigl(\widehat{\mathcal{F}^{(i)}_{0}}, \widehat{\mathcal{F}^{(i)}_{1}}, \ldots\bigr)$
satisfy
\begin{align}
F(\mathcal{F}^{(i)},0,y,t)
& =
\frac{y^{i} t^{i} F(\mathcal{F},0,y,t)^{i}}{(1-t)^{i+1}},
\label{equation_follow_refined}
\\
F(\widehat{\mathcal{F}^{(i)}},0,y,z)
& =
\frac{1}{1+z} \cdot
\left(y z (1+z) C(yz(z+1))\right)^{i} .
\label{equation_follow_refined_full}  
\end{align}
\label{proposition_follow_refined}   
\end{proposition}
When $HTHT$ pairs of arrows do not nest, we obtain a very different
expression enumerating the faces containing backward arrows only. We
employ its {\em dual form}, obtained after reversing all
arrows, using a generalization of the Delannoy numbers.
Recall a {\em Delannoy path} from $(0,0)$ to $(a,b)$ is a lattice path
consisting of North steps $(0,1)$, East steps $(1,0)$ and NE steps
$(1,1)$. The number of Delannoy paths from $(0,0)$ to $(a,b)$ is the
Delannoy number $D_{a,b}$.

\begin{definition}
Given two non-negative integers $a$ and $b$,
the {\em Delannoy polynomial $D_{a,b}(x)$}
is the total weight of all Delannoy paths from $(0,0)$ to $(a,b)$, where
each step contributes a factor of $x$. Thus the coefficient of $x^{j}$ in
$D_{a,b}(x)$ is the number of Delannoy paths from $(0,0)$ to $(a,b)$
having $j$ steps. 
\end{definition}  

\begin{proposition}
Let $\mathcal{F}$ be a family of uniform flag triangulations defined by a
set of rules requiring that $THTH$ type of pairs of arrows
nest. Then the collection $\widehat{\mathcal{F}}$ of families of
saturated faces satisfies
\begin{align}
F(\widehat{\mathcal{F}},x,0,z)
& =
1 + xz \cdot \sum_{a,b\geq 0} D_{a,b}(x) \cdot z^{a+b}. 
\label{equation_saturated_Delannoy}
\end{align}
In particular, the contribution to $F(\widehat{\mathcal{F}},x,0,z)$
of all saturated faces having $a+1$ tails and $b+1$ heads is
$D_{a,b}(x) \cdot xz^{a+b+1}$.
\label{proposition_nest_full}
\end{proposition}  
In our formulas we will often use the following bivariate generating
function of the Delannoy polynomials. We set
\begin{align}
D(u,v,x)
& =
\sum_{a,b\geq 0} u^{a} v^{b} \cdot D_{a,b}(x)
=
\frac{1}{1-x(u+v+uv)} .
\label{equation_Delannoy}
\end{align}





\section{Face enumeration for uniform flag triangulations}
\label{section_Simion}

The following theorem covers half of the uniform flag triangulations in
the Simion class. The analogous result for the remaining triangulations
may be easily obtained using \cref{lemma_dual_enumeration}. 
\begin{theorem}
Let $\mathcal{F}$ be a collection of uniform flag triangulations 
belonging to the Simion class and let $\widehat{\mathcal{F}}$ be the
collection of families of saturated faces. If $THTH$ types of pairs of arrows
do not nest and $HTHT$ types of pairs of arrows nest then the following
identity holds:
\begin{align*}
F(\widehat{\mathcal{F}},x,y,z)
& =
\frac{C(yz(z+1))+z}{1+z}
+
\frac{xz\cdot (1+zC(yz(z+1)))\cdot C(yz(z+1))^{2}}
{(1+z) \cdot (1-2C(yz(z+1))xz-C(yz(z+1))^{2}xz^{2})}. 
\end{align*}
\label{theorem_enumeration_in_the_simion_class}  
\end{theorem}  
By combining
\cref{theorem_enumeration_in_the_simion_class}
and \cref{lemma_all_full} it is possible to
give the generating function of all faces.
%We now explicitly count the facets using
%Corollary~\ref{corollary_facets} and
%equation~\eqref{equation_enumeration_in_the_simion_class}. 
%Since
%\begin{align*}
%F\left(\widehat{\mathcal{F}},\frac{x}{w},\frac{y}{w},wz\right)
%& =
%\frac{C(yz(wz+1))+wz}{1+wz} 
%+
%\frac{xz\cdot (1+wzC(yz(wz+1)))\cdot C(yz(wz+1))^{2}}
%{(1+wz)(1-2C(yz(wz+1))xz-C(yz(wz+1))^{2}xwz^{2})}, 
%\end{align*}
%we obtain that the facet generating function is given by
%\begin{align}
%\sum_{n \geq 0} \sum_{i=0}^{n} f(\triangle_{n},i,n-i) x^{i}y^{n-i}z^{n}
%& =
%C(yz) + \frac{xz\cdot C(yz)^{2}}{1-2xzC(yz)}
%\label{equation_simion_0c_facetgen}  \\
%& =
%C(yz)
%+
%\sum_{i \geq 1}
%2^{i-1} \cdot (xz)^{i} \cdot C(yz)^{i+1}
%\nonumber .
%\end{align}
Extracting the coefficients from the facet generating function yields
the following result. 
\begin{theorem}
Let $\triangle_{n}$ be a uniform flag triangulation of
the boundary $\partial P_{n}$ of the Legendre polytope
belonging to the Simion class satisfying the property that $THTH$ type of
pairs of arrows nest and $HTHT$ type of arrows do not nest.
Then for $i \geq 1$, the number of facets
of $\triangle_{n}$
consisting of $i$ forward arrows and
$n-i$ backward arrows is given by
\begin{align}
f(\triangle_{n}, i, n-i)
& =
2^{i-1} \cdot \frac{(i+1) \cdot (2n-i)!}{(n-i)! \cdot (n+1)!} .
\label{equation_number_of_facets_in_Rodicatope}
\end{align}
The number of facets
of the triangulation $\triangle_{n}$
consisting of no forward arrows and
$n$ backward arrows is given by
the Catalan number $C_{n}$.
\label{theorem_facet_enumeration_class_closest_to_Rodicatope}
\end{theorem}
%\begin{remark}
%{\em The formula (\ref{equation_number_of_facets_in_Rodicatope}) given in
%  Theorem~\ref{theorem_facet_enumeration_class_closest_to_Rodicatope}
%  may be restated as
%\begin{align}
%f(\triangle_{n}, i, n-i)
%& =
%2^{i-1} \cdot C(n,n-i)
%\end{align}
%where the numbers
%$$C(n,k)=\frac{(n+k)! \cdot (n-k+1)}{k! \cdot (n+1)!}$$
%are the numbers in the {\em Catalan triangle}, see sequence A009766
%in~\cite{OEIS}.  
%
%}    
%\end{remark}  


%We end with two observations.
%First, it is amusing how the expression
%in~\eqref{equation_number_of_facets_in_Rodicatope}
%is off by a factor of $1/2$ in the case when $i=0$.
%Second, when $\triangle_{n}$ is
%the Simion type~$B$ associahedron triangulation
%of the boundary of the Legendre polytope,
%it is a possible to give a more
%combinatorial proof of
%Theorem~\ref{equation_number_of_facets_in_Rodicatope}
%by analyzing the tree structure of the digraphs
%corresponding to facets.

Next we look at the revlex class.
\begin{theorem}
\label{theorem_revlex}  
Let $\mathcal{F}$ be a family of uniform flag triangulations in the
revlex class. 
Then the collection $\widehat{\mathcal{F}}$ of families of
saturated faces satisfies
\begin{align}  
\label{equation_revlex_rec}
F(\widehat{\mathcal{F}},x,y,z)
&=
1
+
\sum_{a,b\geq 0}
(x\cdot D_{a,b}(x) + y\cdot D_{a,b}(y)) 
\cdot
z^{a+b+1}
\\
&+
xy
\cdot
\sum_{a^{\prime},b^{\prime},a^{\prime\prime},b^{\prime\prime}\geq 0} D_{a^{\prime},b^{\prime}}(x)
\cdot
D_{a^{\prime\prime},b^{\prime\prime}}(y)
\cdot
z^{a^{\prime}+b^{\prime}+a^{\prime\prime}+b^{\prime\prime}+2}
\cdot 
C(a^{\prime},b^{\prime},a^{\prime\prime},b^{\prime\prime},z)
\nonumber
\end{align}
where
\begin{align}  
C(a^{\prime},b^{\prime},a^{\prime\prime},b^{\prime\prime},z)
&=
\binom{a^{\prime}+b^{\prime\prime}+2}{a^{\prime}+1}
\cdot
\binom{a^{\prime\prime}+b^{\prime}+2}{b^{\prime}+1} \cdot z \\
&+
\binom{a^{\prime}+b^{\prime\prime}+1}{b^{\prime\prime}}
\cdot
\binom{a^{\prime\prime}+b^{\prime}+1}{b^{\prime}}
+
\binom{a^{\prime}+b^{\prime\prime}+1}{a^{\prime}}
\cdot
\binom{a^{\prime\prime}+b^{\prime}+1}{a^{\prime\prime}}.
\nonumber
\end{align}
\end{theorem}  
We obtain a more compact expression using the proof of
\cref{theorem_revlex} by introducing the following generating
function.
\begin{definition}
Let $\widehat{{\mathcal F}}=(\widehat{{\mathcal F}}_{0},
\widehat{{\mathcal F}}_{1}, \ldots)$ be a collection of families of arrows
such that for each~$n$ the family $\widehat{{\mathcal F}_{n}}$ consists of
saturated subsets of $V_{n}$. We define the {\em node-enriched
  exponential generating function} of $\widehat{\mathcal{F}}$ as follows: 
\begin{enumerate}
\item
The empty set (if it belongs to $\widehat{{\mathcal F}}_{0}$)
contributes a factor of $1$.
\item
Each nonempty $\sigma\in \widehat{{\mathcal F}}_{n}$ contributes a term
$$
x^{i} y^{j} \cdot \frac{u^{a+1} \cdot v^{b+1}}{(a+1)! \cdot (b+1)!} \cdot t^{n},
$$
where $i$ is the number of forward arrows, $j$ is the number of backward
arrows, $a+1$ is the number of nodes that are left ends of arrows and
$b+1$ is the number of nodes that are right ends of arrows.   
\end{enumerate}  
\end{definition}  

%It should be noted that the numbers $a+1$ and $b+1$ count the left and
%right ends of arrows and not their heads or tails: a left end is the
%tail of a forward arrow or the head of a backward arrow. A common tail
%of a forward and a backward arrow is counted twice: once as a left end
%and once as a right end. It is easy to derive from the requirements on
%the $THHT$ and $HTTH$ type of pairs of arrows that for the triangulations
%in the revlex class, there is at most one node that is simultaneously
%the left end and the right end of some arrow.

The node-enriched exponential generating function of the saturated
faces in a triangulation in the revlex class has a compact expression in
terms of the following exponential generating function of the Delannoy
polynomials:
\begin{equation}
\Ddd(u,v,x)
=
\sum_{a,b\geq 0} \frac{D_{a,b}(x) \cdot u^{a+1} \cdot v^{b+1}}{(a+1)! \cdot (b+1)!}. 
\end{equation}  

\begin{theorem}
\label{theorem_revlex_exp}  
Let ${\mathcal F}$ be a family of uniform flag triangulations in the
revlex class.
Then the node-enriched exponential generating function of the collection
$\widehat{\mathcal F}$ of families of saturated faces is given by
\begin{align*}
&1+\frac{1}{z} \cdot\Ddd(uz,vz,x)+\frac{1}{z}\cdot \Ddd(vz,uz,y)+\frac{1}{z}
  \cdot\Ddd(uz,vz,x)\cdot\Ddd(vz,uz,y)\\
  &+\frac{1}{z^{2}}\cdot\frac{\partial}{\partial u} \Ddd(uz,vz,x)\cdot
  \frac{\partial}{\partial v}\Ddd(vz,uz,y)
  +\frac{1}{z^{2}}\cdot\frac{\partial}{\partial v} \Ddd(uz,vz,x)\cdot
  \frac{\partial}{\partial u}\Ddd(vz,uz,y). 
\end{align*}  
\end{theorem}  
\cref{theorem_revlex_exp} motivates computing $\Ddd(u,v,x)$
explicitly.
\begin{theorem}
The exponential generating function $\widetilde{D}(u,v,x)$ is given by
$$
\Ddd(u,v,x)
=
\sum_{k \geq 0}
\frac{(uv \cdot (x^{2}+x))^k}{k!^{2}} \cdot \psi_{k+1}(ux) \cdot \psi_{k+1}(vx)  
$$
where $\psi_{k+1}(z)=\frac{d^{k}}{dz^k} \left(\frac{e^z-1}{z}\right)$.  
\label{theorem_psi}
\end{theorem}  
\begin{remark}
  {\em
    It is a direct consequence of \cref{theorem_psi}  that
    $$
    \frac{\partial}{\partial u}\frac{\partial}{\partial v} \Ddd(u,v,x)=
    \exp(x \cdot (u+v))\cdot I_{0}\left(2\sqrt{(x^{2}+x) \cdot uv}\right)
    $$
  where $I_{0}(z)$ is the modified Bessel function of the first kind.  
   } 
\end{remark}  


%\begin{remark}
%{\em
%It can be shown by induction that
%$$ \psi_{k}(z)=\frac{e^{z} \cdot p_{k}(z)+c_{k}}{z^k} , $$
%where $c_{k}=(-1)^{k} \cdot (k-1)!$ and
%$$
%p_{k}(z)=\sum_{i=0}^{k-1} (-1)^{i} \cdot \frac{(k-1)!}{(k-1-i)!} \cdot z^{k-1-i%} .
%$$
%}
%\end{remark} 



Using \cref{corollary_facets} we may count the facets. 

\begin{theorem}
Let $\triangle_n$ be a uniform flag triangulation of the boundary
$\partial P_{n}$ 
of the Legendre polytope that belongs to the revlex class.  
For $1 \leq k \leq n-1$, the number of facets
consisting of $k$ forward arrows and
$n-k$ backward arrows, that is, $f(\triangle_{n},k,n-k)$, is given by
\begin{align*}
\sum_{i=1}^{k}
\sum_{j=1}^{n-k}
\binom{k-1}{i-1}
\binom{n-k-1}{j-1}
\left[
\binom{n-k+i-j}{i}
\binom{k-i+j}{j}
+
\binom{n-k+i-j}{i-1}
\binom{k-i+j}{j-1}
\right].
\end{align*}
The number of facets with $n$ forward arrows and no backward arrows;
and
the number of facets with no forward arrows and $n$ backward arrows
are both equal to $2^{n-1}$.
\label{theorem_reverse_lexicographic_refined_facet_enumeration}
\end{theorem}
Finally we turn our attention to the lex class. 
\begin{theorem}
Let $\triangle_{n}$ be a uniform flag triangulation
of the boundary $\partial P_{n}$ of
the Legendre polytope in the lex class.
Then the number of $(k-1)$-dimensional faces
in the triangulation~$\triangle_{n}$
consisting of $i$ forward arrows and
$k-i$ backward arrows is given by
\begin{align*}
f(\triangle_{n}, i, k-i)
=
\frac{f_{k-1}(\triangle_{n})}{k+1}
& =
\frac{1}{k+1}
\cdot
\binom{n+k}{k}
\cdot
\binom{n}{k} .
\end{align*}
Furthermore, this quantity is independent of the parameter $i$.
\label{theorem_lexicographic_refined_face_enumeration}
\end{theorem}


\acknowledgements{
The first and third authors thank the Institute for Advanced Study in
Princeton, New Jersey for supporting a research visit in Summer 2018.}

\printbibliography





%This work was partially supported by grants from the
%Simons Foundation
%(\#429370 to Richard~Ehrenborg,
%\#245153 and \#514648 to G\'abor~Hetyei,
%\#422467 to Margaret~Readdy). 




%\newcommand{\journal}[6]{{\sc #1,} #2, {\it #3} {\bf #4} (#5), #6.}
%\newcommand{\book}[4]{{\sc #1,} ``#2,'' #3, #4.}
%\newcommand{\bookf}[5]{{\sc #1,} ``#2,'' #3, #4, #5.}
%\newcommand{\arxiv}[3]{{\sc #1,} #2, {\tt #3}.}
%\newcommand{\preprint}[3]{{\sc #1,} #2, preprint {(#3)}.}
%\newcommand{\preparation}[2]{{\sc #1,} #2, in preparation.}





%% if you use biblatex then this generates the bibliography
%% if you use some other method then remove this and do it your own way
%\printbibliography

%\begin{thebibliography}{99}

%\bibitem{Abramowitz-Stegun}
%  \book{M.\ Abramowitz and I.\ A.\ Stegun}
%{Handbook of Mathematical Functions}
%{National Bureau of Standards, Washington, D.C.}{issued 1964, Tenth
%Printing, 1972, with corrections}
  
  
%\bibitem{Ardila_Beck_Hosten_Pfeifle_Seashore}
%\journal{F.\ Ardila, M.\ Beck, S.\ Ho\c{s}ten,
%             J.\ Pfeifle and K.\ Seashore}
%         {Root polytopes and growth series of root lattices}
%         {SIAM J.\ Discrete Math.}
%         {25}{2011}{360--378} 




%\bibitem{Ceballos_Padrol_Sarmiento_old}
%\journal{C.\ Ceballos, A.\ Padrol and C.\ Sarmiento}
%      {Dyck path triangulations and extendability}
%           {J.\ Combin.\ Theory Ser.\ A }
%           {131}{2015}{187--208}
  
%\bibitem{Ceballos_Padrol_Sarmiento}
%\journal{C.\ Ceballos, A.\ Padrol and C.\ Sarmiento}
%      {Geometry of $\nu$-Tamari lattices in
%       types $A$ and $B$}
%           {S\'em.\ Lothar.\ Combin.}
%           {78B}{2017}{Art.\ 68, 12 pp}
%%%      {arXiv:1611.09794 [math.CO]}


%\bibitem{Cellini_Marietti_abelian}
%\journal{P.\ Cellini and M.\ Marietti}
%            {Root polytopes and Abelian ideals}
%            {J.\ Algebr.\ Comb.}
%            {2014}{39}{607--645}

%\bibitem{Cho}
%\journal{S.\ Cho}
%           {Polytopes of roots of type $A_{n}$}
%           {Bull.\ Austral.\ Math.\ Soc.}
%           {59}{1999}{391--402} 


%\bibitem{Cori_Hetyei}
%\journal{R.\ Cori and G.\ Hetyei}
%           {Counting genus one partitions and permutations}
%           {S\'em.\ Lothar.\ Combin.}
%           {70}{2013}{Art.\ B70e, 29 pp}

%\bibitem{deLoera_Rambau_Santos}
%\bookf{J.\ A.\ de Loera, J.\ Rambau and F.\ Santos}
%          {Triangulations: Structures for Algorithms and Applications}
%          {Algorithms Comput.\ Math.\ vol.\ 25}
%          {Springer-Verlag, Berlin}
%          {2010} 

%\bibitem{Ehrenborg_Hetyei_Readdy}
%\journal{R.\ Ehrenborg, G.\ Hetyei and M.\ Readdy}
%            {Simion's type~$B$ associahedron is a pulling triangulation of
%              the Legendre polytope}
%            {Discrete Comput.\ Geom.}
%            {60}{2018}{98--114} 
            

%\bibitem{Ehrenborg_Hetyei_Readdy_Catalan}
%\preparation{R.\ Ehrenborg, G.\ Hetyei and M.\ Readdy}
%              {Very pure monoids and Catalan combinatorics}
            
%\bibitem{Gelfand_Graev_Postnikov}
%            {\sc I.\ M.\ Gelfand, M.\ I.\ Graev and A.\ Postnikov,}
%             Combinatorics of hypergeometric functions associated
%             with positive roots,
%             in Arnold-Gelfand Mathematical Seminars:
%             Geometry and Singularity Theory,
%             Birkh\"auser, Boston, 1996, 205--221.

%\bibitem{Hetyei_Legendre}
%\journal{G.\ Hetyei}
%           {Delannoy orthants of Legendre polytopes}
%           {Discrete Comput.\ Geom.}
%           {42}{2009}{705--721} 






%\bibitem{OEIS}
%  \preprint{OEIS Foundation Inc.}
%  {The On-Line Encyclopedia of Integer Sequences}{\tt http://oeis.org} 


%\bibitem{Oh_Yoo1}
%{\sc S.\ Oh and H.\ Yoo,}
%Triangulations of $\Delta_{n-1} \times \Delta_{d-1}$ and
%          tropical oriented matroids, 
%         23rd International Conference on Formal Power Series and
%          Algebraic Combinatorics (FPSAC 2011), 717--728, 
%         Discrete Math.\ Theor.\ Comput.\ Sci.\ Proc., AO,
%         Assoc.\ Discrete Math.\ Theor.\ Comput.\ Sci., Nancy, 2011.  

%\bibitem{Oh_Yoo_2}
%\arxiv{S.\ Oh and H.\ Yoo}
%             {Triangulations of $\Delta_{n-1} \times \Delta_{d-1}$ and
%          tropical oriented matroids}  
%             {arXiv:1311. 6772v1 [math.CO]}
 

%          
%\bibitem{Postnikov_P}
%\journal{A.\ Postnikov}
%            {Permutohedra, associahedra, and beyond}
%            {Int.\ Math.\ Res.\ Not.\ IMRN}
%            {}{2009}{1026--1106}


     
%\bibitem{Simion}
%\journal{R.\ Simion}
%            {A type-B associahedron}
%            {Adv.\ in Appl.\ Math.} 
%            {30}{2003}{2--25} 





%\bibitem{Sturmfels}
%\book{B.\ Sturmfels}         
%     {Gr\"obner bases and convex polytopes}
%     {University Lecture Series, 8.\ American Mathematical Society,
%       Providence, RI}
%     {1996}

%\end{thebibliography}



\end{document}
