\documentclass[submission]{FPSAC2017}
\articlenumber{32}
\addbibresource{32_Hetyei_Readdy_Ehrenborg.bib}
\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{\vanish}[1]{}
\DeclareMathOperator{\conv}{conv}
\DeclareMathOperator{\DP}{DP}
\DeclareMathOperator{\SP}{SP}
\DeclareMathOperator{\Head}{Head}
\DeclareMathOperator{\Tail}{Tail}
\DeclareMathOperator{\tw}{tw}
\usepackage{amssymb,amsmath,color}
\usepackage{tikz-dependency}
\usepackage{tikz}
\usepackage{enumerate}
\title[Type $B$ associahedron]{Realizing Simion's type $B$
associahedron as a pulling triangulation of the Legendre polytope}
\author[Ehrenborg, Hetyei and Readdy]{Richard
Ehrenborg\thanks{\href{mailto:richard.ehrenborg@uky.edu}{richard.ehrenborg@uky.edu}}\addressmark{1},
G\'abor Hetyei\thanks{\href{mailto:ghetyei@uncc.edu}{ghetyei@uncc.edu}}\addressmark{2} \and Margaret
Readdy\thanks{\href{mailto:margaret.readdy@uky.edu}{margaret.readdy@uky.edu}}\addressmark{1}}
\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}
\received{\today}
\abstract{We show that Simion's type $B$ associahedron is combinatorially
equivalent to a pulling triangulation of a type $B$ root polytope
called the Legendre polytope.
Furthermore, we show that every pulling triangulation of the
Legendre polytope yields a flag complex.
Our triangulation refines a decomposition
of the Legendre polytope given by Cho. We extend Cho's cyclic
group action to the triangulation in such a way that it corresponds to
rotating centrally symmetric triangulations of a regular $(2n+2)$-gon.
\vanish{Finally, we present a bijection between the faces
of the Simion's type~$B$ associahedron
and Delannoy paths.}}
\resume{Nous montrons que l'associa\`edre du type $B$ de Simion est
combinatoriellement \`equivalent \`a une triangulation obtenue en
tirant les sommets d'un polytope des racines du type $B$, appel\'e
le polytope de Legendre. De plus, nous montrons que toute
triangulation obtenue en tirant les sommets de ce polytope est un
complex de drapeau. Notre triangulation raffine une d\'ecomposition du
polytope de Legendre donn\'e par Cho. Nous \'eteignons l'action du
groupe cyclique de Cho \`a la triangulation tel qu'elle correspond \`a
la rotation des triangulations centrallement sym\'etriques d'un $(2n+2)$-gone
r\'egulier.}
\keywords{root polytope, associahedron, type $B$}
\begin{document}
\maketitle
\section{Introduction}
Root polytopes arising as convex hulls of roots in a root system have
become the subject of intensive interest in recent
years~\cite{Ardila,Clark-Ehrenborg,
Gelfand-Graev-Postnikov,Hetyei-Legendre,Meszaros_I,Meszaros_II}.
Another important
area where geometry meets combinatorics is the study of noncrossing
partitions, associahedra and their generalizations. In this context
Simion~\cite{Simion} constructed a type $B$ associahedron whose facets
correspond to centrally symmetric triangulations of a regular $(2n+2)$-gon.
Burgiel and Reiner~\cite{Burgiel-Reiner}
described Simion's construction as
providing ``the first motivating example for an equivariant generalization
of fiber polytopes, that is, polytopal subdivisions which are
invariant under symmetry groups''.
It was recently observed by Cori and Hetyei~\cite{Cori-Hetyei} that the
face numbers in this type $B$ associahedron are the same as the face
numbers in any pulling triangulation of the boundary of a type~$B$ root
polytope, called the Legendre polytope in~\cite{Hetyei-Legendre}.
In this presentation we explain that the equality of these face numbers is not a
mere coincidence: the type~$B$ associahedron is combinatorially
equivalent to a pulling triangulation of the Legendre polytope $P_{n}$. The
convex hull of the positive roots among the vertices of the Legendre
polytope and of the origin is a type $A$ root polytope
$P_{n}^{+}$. Cho~\cite{Cho} has shown that the Legendre polytope $P_{n}$ may be
decomposed into copies of $P_{n}^{+}$ that meet only on their boundaries and
that there is a $\Zzz_{n+1}$-action on this decomposition. Our
triangulation representing the type~$B$ associahedron as a triangulation
of the Legendre polytope refines Cho's decomposition in such a way that
extends the $\Zzz_{n+1}$-action to the
triangulation. The effect of this $\Zzz_{n+1}$-action on the
centrally symmetric triangulations of the $(2n+2)$-gon is rotation.
\vanish{This extended abstract is structured as follows.
In the preliminaries we discuss the Simion type~$B$ associahedron,
the Legendre polytope and pulling triangulations.
In \cref{section_flag}
we show that every pulling triangulation of the Legendre polytope
is a flag complex. We introduce
an arc representation of Simion's type~$B$ diagonals in
\cref{section_arc} and obtain conditions for when a pair of
$B$-diagonals do not cross. A bijection
between the set of $B$-diagonals and the vertex set of the Legendre
polytope is obtained by the intermediary of our arc representation in
\cref{section_embed}. We characterize when $B$-diagonals cross in
terms of crossing and nesting conditions on the arrows associated to the
vertices of the Legendre polytope. This characterization is used in
\cref{section_triangulation} to define a triangulation of the boundary of
the Legendre polytope where each face corresponds to a face in the
type~$B$ associahedron.
Since both complexes are flag and have
the same minimal non-faces,
we conclude that they are the same polytope.
We end this section by
describing the facets in our triangulation.
In \cref{section_Cho}
we prove that our triangulation refines Cho's
decomposition and that his $\Zzz_{n+1}$-action corresponds to
rotating the regular $(2n+2)$-gon.
We conclude with comments and future research directions.}
\section{Preliminaries}
\label{section_preliminaries}
\subsection{Simion's type $B$ associahedron}
Simion~\cite{Simion} introduced a simplicial complex denoted by~$\Gamma_{n}^{B}$
on $n(n+1)$ vertices as follows. Consider a centrally
symmetric convex $(2n+2)$-gon, and label its vertices in the clockwise
order with $1$, $2$, \ldots, $n$, $n+1$, $\overline{1}$, $\overline{2}$,
\ldots, $\overline{n}$, $\overline{n+1}$. The vertices
of $\Gamma_{n}^{B}$ are the {\em $B$-diagonals}, which are one of the two
following kinds: diagonals joining antipodal pairs of points, and
antipodal pairs of noncrossing diagonals. The diagonals joining
antipodal points are all pairs of the form
$\{i,\overline{i}\}$ satisfying $1\leq i\leq n+1$, and they are called
{\em diameters}. The $B$-diagonals
that are antipodal pairs of noncrossing diagonals are either of the form
$\{\{i,j\},\{\overline{i},\overline{j}\}\}$ satisfying $1\leq
i*] (text);
\node[anchor=east] at (2,0.2) (text) {};
\node[anchor=west] at (4,0.2) (description) {};
\draw[line width=0.5mm] (description) edge[out=135,in=45,->] (text);
\end{tikzpicture}
$$
As an example, when $n=7$ then the $B$-diagonal
$\{\{2,5\},\{\overline{2},\overline{5}\}\}$
is represented by the backward arrow $(4,2)$
as drawn above on the interval $(0,8]$.
\item
If the
arc $[u,v-1]$ is not contained in the arc
$[u,n+1]$ then $n+1 < v-1 < u+n+1$.
The integer $\pi(v-1)=v-1-(n+1)$ is congruent to $v-1$ modulo~$(n+1)$
and satisfies $1\leq \pi(v-1)*__] (text);
\node[anchor=east] at (8.3,0) (text) {};
\node[anchor=west] at (5.7,0) (description) {};
\draw[line width=0.5mm] (description) edge[out=0,in=180,->] (text);
\node[anchor=east] at (6.2,0.2) (text) {};
\node[anchor=west] at (2.8,0.2) (description) {};
\draw[line width=0.5mm] (description) edge[out=45,in=135,->] (text);
\end{tikzpicture}
$$
For instance, when $n = 7$
the $B$-diagonal $\{\{4,\overline{6}\},\{\overline{4},6\}\}$
yields the forward arrow $(3,6)$.
\end{enumerate}
}
\end{remark}
\begin{proposition}
\label{proposition_crossing_pi}
The $B$-diagonal represented by the arrow $(\pi(v_{1}-1),\pi(u_{1}))$ and
the $B$-diagonal represented by the arrow $(\pi(v_{2}-1),\pi(u_{2}))$
are noncrossing if and only if the images $\pi([u_{1},v_{1}-1])$ and
$\pi([u_{2},v_{2}-1])$ are disjoint or contain each other.
\end{proposition}
\vanish{\begin{proof}
The statement is an easy consequence of the following observation.
Both arcs of the arc representation $\{[u,v-1],[u+n+1,v+n]\}$ of a
$B$-diagonal are mapped onto the same arc $[\pi(u),\pi(v-1)]$ by
$\pi$ and $[u,v-1]\cup [u+n+1,v+n]=\pi^{-1}([\pi(u),\pi(v-1)])$.
\end{proof}}
\vanish{
Next we translate the noncrossing conditions for $B$-diagonals into
conditions for the arrows representing them.}
\begin{proposition}
\label{proposition_across}
Suppose a pair of $B$-diagonals is represented by a pair of arrows as
defined in \cref{definition_arrow_representation}.
These $B$-diagonals cross
if and only if one of the following conditions is satisfied:
\begin{enumerate}[(1)]
\itemsep=-5pt
\item Both arrows are backward and they cross.
\item Both arrows are forward and they do not nest.
\item One arrow is forward, the other one is backward, and
the backward arrow nests or crosses the forward arrow.
\item The head of one arrow is the tail of the other arrow.
\end{enumerate}
\end{proposition}
\vanish{\begin{proof}
Suppose the arc representations of the two $B$-diagonals are
$\{[u_{1},v_{1}-1],[u_{1}+n+1,v_{1}+n]\}$ and $\{[u_{2},v_{2}-1],[u_{2}+n+1,v_{2}+n]\}$,
respectively. By \cref{proposition_crossing_pi}, the represented $B$-diagonals
are crossing if and only if the images
$\pi([u_{1},v_{1}-1])$ and
$\pi([u_{2},v_{2}-1])$
are not disjoint and do not contain each other.
We will consider three cases, depending on the
direction of the two arrows $(\pi(v_{1}-1),\pi(u_{1}))$ and
$(\pi(v_{2}-1),\pi(u_{2}))$. These arrows are either both forward,
both backward or have opposite directions.
If both arrows are backward then neither the image
$\pi([u_{1},v_{1}-1])$ nor the image $\pi([u_{2},v_{2}-1])$
contain the point $n+1$.
Two such intervals intersect nontrivially in an interval of positive length
exactly when the corresponding arrows cross. They intersect in a
single point exactly when there is a vertex that is the tail of one of
the arrows and the head of the other arrow.
If both arrows are forward then both images
$\pi([u_{1},v_{1}-1])$ and $\pi([u_{2},v_{2}-1])$ contain
the point $n+1$, so they cannot be disjoint. They do not contain each
other exactly when the corresponding arrows are not nested. Note that a
pair of forward arrows such that the head of one arrow is the same as
the tail of the other is particular example of a pair of nonnested arrows.
Assume finally that one of the arrows, say $(\pi(v_{1}-1),\pi(u_{1}))$,
is a backward arrow and the other one, say $(\pi(v_{2}-1),\pi(u_{2}))$,
is a forward arrow. The image $\pi([u_{2},v_{2}-1])$
cannot be a
subset of $\pi([u_{1},v_{1}-1])$ as the first image contains
the point $n+1$ whereas the second does not.
The image $\pi([u_{1},v_{1}-1])$
is the interval $[\pi(u_{1}),\pi(v_{1}-1)]$,
whereas
the image $\pi([u_{2},v_{2}-1])$
is the union $(0,\pi(v_{2}-1)] \cup [\pi(u_{2}),n+1]$.
The intersection of these two sets has either
zero, one or two connected components.
If one component is a single point
then this point is the head of one arrow
and the tail of the other.
If both components are non-trivial
intervals then the backward
arrow nests the forward arrow.
If they intersect in one interval
but the image $\pi([u_{1},v_{1}-1])$
does not contain
the image $\pi([u_{2},v_{2}-1])$
then the two arrows cross.
Finally, if the image $\pi([u_{1},v_{1}-1])$
does contain
the image $\pi([u_{2},v_{2}-1])$
then the arrows neither cross nor nest.
\end{proof}}
\vanish{An immediate consequence of
\cref{proposition_across}
and \cref{lemma_facets}
is the following corollary.}
\begin{corollary}
Noncrossing sets of $B$-diagonals are represented by subsets of vertices
contained in a facet of the Legendre polytope $P_{n}$.
\end{corollary}
\section{The type $B$ associahedron represented
as a pulling triangulation}
\label{section_triangulation}
\vanish{In this section we show that the arc representation given in
\cref{definition_arrow_representation}
constitutes
Simion's type~$B$ associahedron $\Gamma_{n}^{B}$
as a pulling triangulation of the boundary of the Legendre polytope $P_{n}$.
Our main result is the following.}
\begin{theorem}
\label{theorem_r_pull}
Let $<$ be any linear order on the vertex set of $P_{n}$ subject to the
following conditions:
\begin{enumerate}
\itemsep=-5pt
\item $(x_{1},y_{1})<(x_{2},y_{2})$
whenever $x_{1}-y_{1} > 0 > x_{2}-y_{2}$.
\item On the subset of vertices $(x,y)$ satisfying $xy$, we have
$(x_{1},y_{1})<(x_{2},y_{2})$ whenever the interval $[y_{1},x_{1}]$ is contained in
the interval $[y_{2},x_{2}]$.
\end{enumerate}
Then the arc representation of $\Gamma_{n}^{B}$ given in
\cref{definition_arrow_representation} is a pulling triangulation of the boundary
of the Legendre polytope $P_{n}$ with respect to $<$.
\end{theorem}
The main idea of the proof is the following.
Recall that $\Gamma_{n}^{B}$ is a flag complex and its
minimal nonfaces are the pairs of crossing $B$-diagonals.
By \cref{theorem_pull_flag} the pulling triangulation we
defined is also a flag complex. It suffices to show that the minimal
nonfaces are in bijection. Equivalently,
for any pair of arrows $\{(x_{1},y_{1}),(x_{2},y_{2})\}$ that form an edge in
the pulling triangulation of $P_{n}$,
these arrows correspond to a pair of noncrossing
$B$-diagonals in~$\Gamma_{n}^{B}$.
By \cref{proposition_across} this amounts to showing the
following: backward arrows cannot cross, forward arrows must nest, and
for a pair of arrows of opposite direction the backward arrow cannot
cross or nest the forward arrow. The rest of the proof is an easy
verification of these statements for the six possible relative positions
of a pair of arrows with distinct endpoints.
\vanish{\begin{proof}
Fix any pulling order $<$ satisfying the above conditions.
The first condition requires all backward arrows to precede all
forward arrows.
The next two conditions require that for a pair
of nested arrows of the same direction the nested arrow should precede
the nesting arrow.
\newcommand{\lift}[1]{\raisebox{2.5mm}{#1}}
\newcommand{\TheTable}{
\begin{table}[t]
\begin{tabular}{|c||c|c|c|}
\hline
Order of nodes & Arrow first pulled & Edge & Not an edge\\
\hline
\hline
\lift{$x_{1}1$.
\item If $k=1$ then there is no forward arrow in the set $S$.
\item Forward arrows must nest. In particular, if $k>1$ then for each
each forward arrow $(x,y)\in S$ must satisfy $x\leq k-1$
and $y \geq k$. (Forward arrows must nest $(k-1,k)$.)
\item
No head of an arrow in the set $S$
is also the tail of another arrow in $S$.
\item No two arrows cross.
\end{enumerate}
\end{theorem}
\vanish{\begin{proof}
Condition~(1) is equivalent to
\cref{lemma_diameter}.
Except for Condition~(3), the remaining conditions are stated for all
faces in \cref{proposition_across}. To prove Condition~(3), observe
that $k=1$ implies that the backward arrow $(n+1,1)$ belongs to
$S$. This arrow would nest any forward arrow, contradicting
Condition~(3) in \cref{proposition_across}.
\end{proof}}
\section{Triangulating Cho's decomposition}
\label{section_Cho}
The type $A$ root polytope $P_{n}^{+}$
is the convex hull of the origin and the set of points
$\{e_{i} - e_{j} \: :\: 1 \leq i < j \leq n+1\}$.
Cho~\cite{Cho} gave a decomposition
of the Legendre polytope~$P_{n}$
into $n+1$ copies of $P_{n}^{+}$ as follows. The symmetric group
$\SSSS_{n+1}$ acts on the Euclidean space $\Rrr^{n+1}$ by
permuting the coordinates, that is, the permutation
$\sigma \in \SSSS_{n+1}$ sends the
basis vector $e_{i}$ into $e_{\sigma(i)}$. Hence the permutation~$\sigma$
acts on the Legendre polytope $P_{n}$ by sending each $e_{i}-e_{j}$ into
$e_{\sigma(i)}-e_{\sigma(j)}$.
Cho's main result~\cite[Theorem~16]{Cho} is
the following decomposition.
\begin{theorem}[Cho]
The Legendre polytope $P_{n}$ has the decomposition
$$ P_{n} = \bigcup_{k=0}^{n} \zeta^{k}(P_{n}^{+}) $$
where $\zeta$ is the cycle $(1,2,\ldots,n+1)$.
Furthermore, for $0 \leq k < r \leq n$
the polytopes $\zeta^{k}(P_{n}^{+})$ and $\zeta^{r}(P_{n}^{+})$
have disjoint interiors.
\label{theorem_Cho}
\end{theorem}
The following theorem implies that each copy $\zeta^{k}(P_{n}^{+})$ of
$P_{n}^{+}$ is the union of simplices of the triangulation given in
\cref{definition_arrow_representation}, representing the
boundary complex $\Gamma_{n}^{B}$ of Simion's type $B$ associahedron.
\begin{theorem}
Every facet $F$ of the arc representation of $\Gamma_{n}^{B}$ given in
\cref{definition_arrow_representation} is contained in
$\zeta^{k-1}(P_{n}^{+})$
where $k$ is the unique arrow of the form $(k-1,k)$ in $F$
or $(n+1,1)$ if $k=1$.
Equivalently, the facet $F$ is contained in $\zeta^{k}(P_{n}^{+})$
exactly when it represents a facet of $\Gamma_{n}^{B}$
that contains the diagonal~$\{k,\overline{k}\}$.
\end{theorem}
\vanish{\begin{proof}
The polytope $P_{n}^{+}$ is the convex hull the origin and of all vertices that are
represented by backward arrows. The facets of type $1$ (as defined in
\cref{theorem_arrow}) form a pulling triangulation of the part of the
boundary of $P_{n}^{+}$ that does not contain the origin. In fact, the
restriction of the pulling order to the backward arrows may be taken in the
{\em revlex order}, as defined in \cite[Definition~4.5]{Hetyei-Legendre}, giving
rise to the {\em standard triangulation} described
in~\cite{Gelfand-Graev-Postnikov}. A facet in our triangulation of $P_{n}$
belongs to the standard triangulation of the boundary of the part of
$P_{n}^{+}$ not containing the origin exactly when it has type $1$.
Observe next that the effect of $\zeta$ on the arrows (considered as
vertices of $P_{n}$) is adding $1$ modulo $n+1$ to the head and to the
tail of each arrow. Taking into account
\cref{definition_arrow_representation}
and
\cref{remark_arrows}, it is not difficult to see that the induced effect
on the arc representation is adding $1$ modulo $n+1$, that is, a
rotation. It is worth noting that to rotate each vertex of a regular
$(2n+2)$-gon into itself requires increasing each index by one $2n+2$
times. However, a centrally symmetric pair of arcs $\{[u, v-1], [u+n+1,
v+n]\}$ is taken into itself already by $n+1$ such elementary
rotations. In the arc representation the facets containing only backward
arrows corresponding to facets containing the pair of arcs
$\{[1,n+1],[n+2,2n+2]\}$. The induced action of $\zeta^{k-1}$ takes this
pair into $\{[k,n+k],[n+k+1,2n+1+k]\}$. The conditions stated in
\cref{theorem_across} are rotation-invariant, so the induced action
of $\zeta^{k-1}$ takes the family of all facets containing
$\{[1,n+1],[n+2,2n+2]\}$ into the family of all facets containing
$\{[k,n+k],[n+k+1,2n+1+k]\}$.
\end{proof}}
\section{Concluding Remarks}
For complete proofs, we refer the reader to the full length
version of this extended abstract~\cite{Ehrenborg-Hetyei-Readdy}.
Simion observed algebraically that the number of $k$-dimensional
faces of the type~$B$ associahedron is given by the number of {\em balanced
Delannoy paths} between $(0,0)$ and $(2n,0)$ taking
$k$ up steps $(1,1)$, $k$ down steps $(1,-1)$, and $n-k$ horizontal
steps $(2,0)$. We have found a combinatorial proof by providing
a non-recursive bijection between the faces of the type~$B$ associahedron
and Delannoy paths~\cite[Section~8]{Ehrenborg-Hetyei-Readdy}.
In a recent paper, Cellini and Marietti~\cite{Cellini_Marietti_abelian} used
abelian ideals to produce a triangulation for various root polytopes.
In the case of type $A$, their
construction yields once again a lexicographic triangulation of
each face. Restricting to the positive roots yields Gelfand, Graev
and Postnikov's anti-standard tree bases for the type $A$ positive
root polytope. Is there an ideal corresponding to the reverse
lexicographic triangulation?
The $h$-vector of Simion's type~$B$ associahedron
may be computed from the $f$-vector using
elementary operations on binomial coefficients;
see~\cite[Corollary 1]{Simion}.
\begin{lemma}[Simion]
The $h$-vector $(h_{0}, h_{1}, \ldots, h_{n})$ of
Simion's type~$B$ associahedron~$\Gamma_{n}^{B}$ satisfies
$$
h_{i}=\binom{n}{i}^{2}\quad \mbox{for $0\leq i\leq n$}.
$$
\end{lemma}
\noindent
One of the referees
pointed out the recent work of Ceballos, Padrol and
Sarmiento, in which
they recover our pulling triangulation of the bounday of the Legendre
polytope~\cite[Theorem 8.5]{Ceballos-Padrol-Sarmiento}.
Much earlier Billera, Cushman and Sanders describe
an explicit shelling using lattice paths
and recover the values $h_i$ as counting those lattice
paths having~$i$ corners~\cite[Section 3]{Billera_Cushman_Sanders}.
The fact that the number of such lattice paths
is given by
$\binom{n}{i}^{2}$ is a classical result
of MacMahon from 1915~\cite[Vol.\ I, Article~89, pp.~119-120]{MacMahon}.
Finally, are there other interesting simplicial polytopes that
can be better understood as pulling triangulations of less
complicated polytopes?
\acknowledgements{The first author was partially funded by
the National Security Agency grant H98230-13-1-028.
This work was partially supported by two grants from the
Simons Foundation
(\#245153 to G\'abor Hetyei and \#206001 to Margaret Readdy).
The authors thank the Princeton University Mathematics Department
where this research was initiated, and two anonymous referees for many
insightful comments.}
\printbibliography
\end{document}
__