<figure><img src="image_1.png" /><figcaption>**Fig. 1:** (Left) Two polytopal realizations of the 3-dimensional associahedron, with vertices labeled by triangulations of convex hexagons [Lod04, HL07, LP13]. (Right) Two 3-dimensional tree associahedra, with vertices labeled by maximal nested sets of tubes of the trees [CD06, Dev09, Pos09].</figcaption></figure>

More recently, M. Carr and S. Devadoss [CD06, Dev09] defined and constructed graph associahedra. Given a finite graph G, a G-associahedron is a simple convex polytope which encodes the connected subgraphs of G and their nested structure. More precisely, the face lattice of its polar is isomorphic to the *nested complex* on G, defined as the simplicial complex of all collections of tubes (connected induced subgraphs) of G which are pairwise either nested, or disjoint and non-adjacent. See Figure 1 (right) for 3-dimensional examples. Certain graph associahedra coincide with well-known polytopes: classical associahedra are path associahedra, cyclohedra are cycle associahedra, and permutahedra are complete graph associahedra. Different polytopal realizations of the G-associahedron were constructed [CD06, Dev09, Pos09, FS05, Zel06], but all with the same normal fan: its rays are the characteristic vectors of the tubes of G and its cones are the cones over the nested sets of G. For example, the normal fan of these realizations of the path associahedron is always that of J.-L. Loday's associahedron [Lod04].

In view of the combinatorial diversity of C. Hohlweg and C. Lange's realizations of the (path) associa-
hedron, it seems natural to look for similar constructions for the graph associahedra. Such constructions
would yield in particular geometrically distinct normal fans and different poset structures on maximal
nested sets, exactly as C. Hohlweg and C. Lange's associahedra yield different Cambrian lattices and
fans [Rea06]. This paper is a first step towards this direction: it focusses on the case of tree associahedra.

Due to space limitation, we only present our main results and skip all proofs in this extended abstract.
They can be found in the complete version [Pil13], as well as further topics and many more illustrations.

2 Signed nested complexes

We fix a finite *signed ground set* $V = V^{-} \sqcup V^{+}$ with $\nu$ elements, partitioned into a negative set $V^{-}$ and a positive set $V^{+}$. For any $X \subseteq V$, we set $X^{-} := X \cap V^{-}$ and $X^{+} := X \cap V^{+}$, and we write $X = X^{-} \sqcup X^{+}$.
We also fix a *signed ground tree* $T$, whose vertex set is the signed ground set $V$. For example, consider the signed ground tree $T^{\text{ex}}$ on the signed ground set $V^{\text{ex}} := \{1, 3, 4, 5\} \sqcup \{0, 2, 6, 7, 8, 9\}$ represented in Figure 2 (left). Its negative vertices are colored in white, while its positive ones are colored in black.

**Definition 1** A subset *B* of *V* is negative convex (resp. positive convex) in *T* if any negative (resp. positive) vertex lying on the unique path in *T* between two vertices of *B* is also in *B*. A signed building block of *T* is a non-empty proper subset *B* of *V* which is negative convex and whose complement *V* \ *B* is positive convex. The signed building set of *T* is the collection *B*(*T*) of all signed building blocks of *T*.
**Definition 2** Two signed building blocks $B_1, B_2 \in \mathcal{B}(T)$ are compatible if either $B_1 \subseteq B_2$, or $B_1 \supseteq B_2$, or $B_1 \cap B_2 = \emptyset$ and $B_1 \cup B_2 \notin \mathcal{B}(T)$, or $B_1 \cup B_2 = V$ and $B_1 \cap B_2 \notin \mathcal{B}(T)$. The signed nested complex $\mathcal{N}(T)$ is the simplicial complex of all collections of pairwise compatible signed building blocks of $T$.

For example, the sets $\{0, 1, 3\}$, $\{0, 1, 2, 3, 5, 7\}$, and $\{9\}$ are pairwise compatible signed building blocks for the signed ground tree $T^\text{ex}$ of Figure 2 (left). In contrast, none of them is compatible with the signed building block $\{1, 3, 4, 5\}$. Although we will not need it in this extended abstract, the signed building sets and their compatibility relation can be defined using alternative perspectives, see [Pil13] for details.

**Example 3 (Unsigned trees)** When $T$ has only negative vertices, the building sets on $T$ are precisely the connected subtrees of $T$, and they are compatible when they are either nested, or disjoint and non-adjacent. Therefore, our definition matches the classical nested complex on $T$, see [CD06, Pos09, Zel06].

**Example 4 (Signed paths)** When $T$ is a signed path, the signed nested complex $\mathcal{N}(T)$ is isomorphic to the $(\nu - 1)$-dimensional simplicial associahedron. The correspondence between the signed building sets of $\mathcal{B}(T)$ and the internal diagonals of the $(\nu + 2)$-gon depends on the signature of $T$, see [HL07, Pil13].

Contrarily to the simple situation of Example 4, the signed nested complex $\mathcal{N}(T)$ depends in general both on the combinatorial structure of the tree $T$ and on the signs of its vertices. Nevertheless, the following statement gives sufficient conditions for the signed nested complexes defined by two signatures on the same underlying unsigned tree to be isomorphic. These conditions covers the situations of paths and stars.

**Proposition 5** Let $T$ be a signed tree and let $T'$ be obtained from $T$ by one of the following operations:

(i) changing simultaneously the signs of all vertices of $T$,

(ii) changing the sign of a leaf of $T$,

(iii) switching two vertices of $T$, adjacent to each other and of degree at most 2.

Then the signed nested complexes $\mathcal{N}(T)$ and $\mathcal{N}(T')$ are isomorphic.

# 3 Signed spines

In this section, we introduce spines on a signed ground tree $T$, generalizing the definition of *spines* (or *mixed cobinary trees*) given in [LP13] and [IO13] for the path associahedron. We interpret the signed nested complex $\mathcal{N}(T)$ in terms of the contraction poset on signed spines on $T$, and its dual graph in terms of flips between maximal signed spines on $T$. When $T$ is an unsigned path, maximal spines are binary search trees, flips are rotations on binary trees, and spines are Schröder trees.

## 3.1 Signed spine poset

Consider a directed tree $S$ whose vertices are labeled by non-empty subsets of $V$. If $r$ is an arc of $S$, we call *source label set* of $r$ in $S$ the union $\text{sc}(r)$ of all labels which appear in the connected component of $S \setminus r$ containing the source of $r$. The *sink label set* $\text{sk}(r)$ of $r$ is defined similarly.

**Definition 6** A signed spine on $T$ is a directed and labeled tree $S$ such that

(i) the labels of the nodes of $S$ form a partition of the signed ground set $V$, and

(ii) at a node of $S$ labeled by $U = U^- \sqcup U^+$, the source label sets of the different incoming arcs are subsets of distinct connected components of $T \setminus U^-$, while the sink label sets of the different outgoing arcs are subsets of distinct connected components of $T \cup U^+$.
Besides the signed ground tree $T^{\text{ex}}$, Figure 2 represents three examples of signed spines on $T^{\text{ex}}$. In their labels, we distinguish the negative vertices in white from the positive vertices in black. For example, the vertex $\textcircled{368}$ of the first spine has negative vertices $\{3\}$ and positive vertices $\{6, 8\}$. We can check the local Condition (ii) of Definition 6 around this vertex: indeed $\{0, 1\}$, $\{5\}$ and $\{4, 9\}$ are subsets of distinct connected components of $T^{\text{ex}} \setminus \{3\}$, while $\{2\}$ and $\{7\}$ are subsets of distinct connected components of $T^{\text{ex}} \setminus \{6, 8\}$. The reader is invited to check that this condition holds around each node of the three spines.

<figure><img src="image_2.png" /><figcaption>**Fig. 2:** Three signed spines (right) on the signed ground tree $T^{\text{ex}}$ (left).</figcaption></figure>

We now consider arc contraction and arc insertion in signed spines. For example on Figure 2, the first spine can be obtained by arc contractions from the other two spines.

**Lemma 7** (i) Contracting any arc in a signed spine on $T$ leads to a new signed spine on $T$.

(ii) Let $S$ be a signed spine on $T$ with a node $s$ labeled by a set $U$ containing at least two elements. For any $u \in U$, there exists a signed spine $S'$ on $T$ whose nodes are labeled exactly as that of $S$, except that the node $s$ of $S$ splits into two nodes in $S'$, respectively labeled by $\{u\}$ and by $U \setminus \{u\}$.

This lemma shows that the contraction poset on the signed spines on $T$ is a pure graded poset of rank $\nu$. The next statement connects this contraction poset to the signed nested complex studied in Section 2.

**Theorem 8** (i) For any arc $r$ of a spine $S$ on $T$, the source label set $sc(r)$ is a signed building set of $T$.

(ii) For any spine $S$ on $T$, the collection $B(S) := \{sc(r) \mid r \text{ arc of } S\}$ is a signed nested set of $\mathcal{N}(T)$.

(iii) The map $B$ defines a poset isomorphism from the contraction poset on the spines of $T$ to the face poset of the signed nested complex $\mathcal{N}(T)$.

**Corollary 9** The signed nested complex $\mathcal{N}(T)$ is a pure simplicial complex of dimension $\nu - 1$.

**Example 10 (Unsigned paths)** When $T$ is a path labeled by $[\nu]$ increasingly from one leaf to the other and with only negative signs, the maximal spines on $T$ are the binary search trees on $[\nu]$, i.e. where the label of each node is larger than all labels in its left child, and smaller than all labels in its right child.

**Example 11 (Unsigned trees)** When $T$ has only negative vertices, the spines are just the inclusion posets of the nested sets of $\mathcal{N}(T)$. They are called $\mathcal{B}$-trees by A. Postnikov [Pos09].

**Example 12 (Signed paths)** When $T$ is a signed path, the signed spines on $T$ are directed and labeled dual binary trees of dissections of a $(\nu+2)$-gon. These trees are used in [LP13] to survey the construction of [HL07] and to derive an independent proof of it, and in [IO13] for more algebraic purposes.
## 3.2 Flips in maximal signed spines

We now define flips in spines, an operation which transforms a maximal signed spine $S$ on $T$ into a new one $S'$ such that $B(S)$ and $B(S')$ are adjacent facets of the signed nested complex $N(T)$. Since we deal with maximal spines here, the nodes of $S$ are labeled by singletons. We therefore abuse notation by identifying a node with the unique element of its label.

**Definition 13** Consider an arc $r$ in a maximal signed spine $S$ on $T$, from a node $u \in V$ to a node $v \in V$. If they exist, let $i$ denote the incoming arc of $S$ at $u$ whose source label set lies in the connected component of $T \setminus \{u\}$ containing $v$ and let $o$ denote the outgoing arc of $S$ at $v$ whose sink label set lies in the connected component of $T \setminus \{v\}$ containing $u$. Let $S'$ denote the tree obtained from $S$ by reversing the arc $r$ to an arc $r'$ from $v$ to $u$, and attaching the arc $i$ to $v$ and the arc $o$ to $u$. We say that $S'$ is obtained from $S$ by flipping $r$, and that $S$ and $S'$ are related by a flip.

For example, the two maximal spines of Figure 2 are obtained from each other by flipping the arc 3–8. Figure 3 illustrates the four possible situations, according on whether $u$ and $v$ belong to $V^-$ or $V^+$.

<figure><img src="image_3.png" /><figcaption>**Fig. 3:** Flipping an edge in a maximal signed spine. The four possible situations (whether $u$ and $v$ belong to $V^-$ or $V^+$) are illustrated. White nodes represent negative nodes while black nodes represent positive nodes.</figcaption></figure>

**Proposition 14** The tree $S'$ is a signed spine on $T$. Moreover, $S$ and $S'$ are the only two maximal signed spines on $T$ refining the spine $\bar{S}$ obtained from $S$ (or $S'$) by contracting the arc $r$ (or $r'$).

**Corollary 15** The signed nested complex $N(T)$ is a closed pseudo-manifold.

**Example 16 (Unsigned paths)** When $T$ is a path with only negative signs (see Example 10), the flip operation is the rotation in binary search trees, which is used in algorithms to balance them.

**Example 17 (Signed paths)** When $T$ is a signed path, arc flips on maximal spines corresponds to diagonal flips on the triangulations of the $(\nu + 2)$-gon. See [LP13] for details.

# 4 Spine fan

In this section, we construct a geometric realization of the signed nested complex $N(T)$ as a complete simplicial fan. We call it the *spine fan* since it is obtained from the signed spines on $T$. It coarsens the braid fan, defined by the braid arrangement in $\mathbb{R}^V$. We start by a brief reminder on the braid fan and its relation to preposet cones. More details can be found in [PRW08].
## 4.1 Braid fan and preposet cones

We consider the braid arrangement on $\mathbb{R}^V$, defined as the collection of hyperplanes $\{\mathbf{x} \in \mathbb{R}^V \mid x_u = x_v\}$ for $u \neq v \in V$. Since this arrangement is not essential (the intersection of all these hyperplanes contains the line directed by $\mathbb{I} := \sum_{v \in V} e_v$), we consider its intersection with the hyperplane $\mathbb{H}$ of $\mathbb{R}^V$ defined by

$$ \mathbb{H} := \{ \mathbf{x} \in \mathbb{R}^V \mid \sum_{v \in V} x_v = \begin{pmatrix} \nu + 1 \\ 2 \end{pmatrix} \}, $$

where $\nu = |V|$. The braid arrangement defines on $\mathbb{H}$ a complete simplicial fan that we call the *braid fan* and denote by $\mathcal{BF}(V)$. It is the normal fan of the permutahedron $\text{Perm}(V)$, see Section 5.1. Its $k$-dimensional cones correspond to the *surjections* from $V$ to $[k+1]$, or equivalently to the *ordered partitions* of $V$ into $k+1$ parts. For example, the maximal cones of $\mathcal{BF}(V)$ correspond to the $\nu!$ linear orders on $V$, while the rays of $\mathcal{BF}(V)$ correspond to the $2^\nu - 2$ proper and non-empty subsets of $V$. See Figure 4 (left).

<figure><img src="image_4.png" /><figcaption>**Fig. 4:** The 3-dimensional braid fan $\mathcal{BF}([4])$ is the normal fan of the 3-dimensional permutahedron $\text{Perm}([4])$.</figcaption></figure>

The braid fan $\mathcal{BF}(V)$ provides geometric representations of certain order structures on $V$. A preposet on $V$ is a binary relation $R \subseteq V \times V$ which is reflexive and transitive. Hence, any equivalence relation is a symmetric preposet and any poset is an antisymmetric preposet. Any preposet $R$ can in fact be decomposed into an equivalence relation $\equiv_R := \{(u, v) \in R \mid (v, u) \in R\}$, together with a poset structure $\prec_R := R/\equiv_R$ on the equivalence classes of $\equiv_R$. Consequently, there is a one-to-one correspondence between preposets and acyclic oriented graphs on subsets of $V$ whose vertices partition $V$: a preposet $R$ corresponds to the Hasse diagram of the poset $\prec_R$ on the equivalence classes of $\equiv_R$, and conversely, an acyclic oriented graph whose vertex set partitions $V$ corresponds to its transitive closure.

The *braid cone* of a preposet $R$ on $V$ is the cone $C(R) := \{\mathbf{x} \in \mathbb{H} \mid x_u \leq x_v, \text{ for all } (u, v) \in R\}$. For example, the cones of the braid fan $\mathcal{BF}(V)$ are precisely the cones of the *linear preposets*, i.e. the preposets $L$ on $V$ whose associated poset $\prec_L$ is a linear order on the equivalence classes of $\equiv_L$. The dimension of $C(R)$ is the number of equivalence classes of the relation $\equiv_R$ minus 1. The normal vectors of the facets of $C(R)$ are the incidence vectors of the arcs of the Hasse diagram of $\prec_R$. We will use the following dictionary between combinatorial properties of preposets and geometric properties of their braid cones (see [PRW08] for details):
1. If $R$ and $R'$ are two preposets on $V$, then the cone $C(R)$ contains the cone $C(R')$ if and only if $R'$ is an extension of $R$, i.e. $R \subseteq R'$ as a subset of $V \times V$.

2. The cone $C(R)$ of any preposet $R$ is the (disjoint) union of the (relative interiors of the) cones of its linear extensions. In particular, the cone $C(\prec)$ of a poset $\prec$ is the union of the total linear extensions of $\prec$, i.e. the linear orders on $V$ which respect the relations in $\prec$.

3. The cone $C(R)$ is simplicial if and only if the Hasse diagram of $\prec_R$ is a directed tree. The rays of $C(R)$ are then the characteristic vectors of the source label sets of the arcs of this tree.

## 4.2 Spine fan

Consider a signed spine $S$ on $T$. Since $S$ is a directed tree labeled by a partition of $V$, its transitive closure is a preposet on $V$. We let $C(S) := \{\mathbf{x} \in \mathbb{H} \mid x_u \le x_v, \text{ for all paths } u \to v \text{ in } S\}$ be the cone of this preposet. The cones of the signed spines on $T$ obtained by contraction of the spine $S$ are faces of the cone $C(S)$. Moreover, the cone $C(S)$ is obtained by glueing some cones $C(\prec)$ of linear preposets $\prec$ on $V$: namely, the cone $C(S)$ is the union of the cones $C(\prec)$ over all linear extensions $\prec$ of $S$ (meaning that $u \prec v$ for any $u, v \in V$ such that $u$ is below $v$ in $S$). The following statement is the main result of this section and prepares the foundations for the polytopal realizations of $\mathcal{N}(T)$ to be constructed in Section 5.

**Theorem 18** *The collection of cones $\mathcal{F}(T) := \{C(S) \mid S \in \mathcal{S}(T)\}$ defines a complete simplicial fan on $\mathbb{H}$, which we call the spine fan. This fan is isomorphic to the signed nested complex $\mathcal{N}(T)$.*

**Corollary 19** *For any signed tree $T$, the signed nested complex $\mathcal{N}(T)$ is a simplicial sphere.*

**Example 20 (Unsigned trees)** For unsigned trees, the spine fan is the nested fan, which is the normal fan of all known polytopal realizations of the tree associahedron [CD06, Dev09, Pos09, FS05, Zel06].

**Example 21 (Signed paths)** For signed paths, the spine fans are the type A Cambrian fans of N. Reading and D. Speyer [RS09]. Following [Rea06], we study below the combinatorial properties of the surjection map defined by these simplicial fans.

## 4.3 Surjection map and T-congruence

The following statement, implicit in Theorem 18, connects geometrically the braid fan to the nested fan.

**Proposition 22** *Any linear order $\prec$ on $V$ extends a unique maximal signed spine $\kappa(\prec)$ of $T$.*

It defines a surjection $\kappa$ from the linear orders on $V$ to the maximal signed spines on $T$: the image $\kappa(\prec)$ of a linear order $\prec$ is the unique maximal signed spine on $T$ for which $\prec$ is a linear extension.

Similar to N. Reading's procedure in [Rea06], there is an insertion algorithm to compute the image of a linear order $\prec$ under the surjection $\kappa$. Details can be found in [Pi13]. When $T$ is an unsigned path, this procedure can be described in terms of insertion in binary search trees, see [Lod04, HNT02].

Rather than the image, we want here to understand the fibers of $\kappa$. In other words, we want to characterize the subsets of linear orders on $V$ which extend the same maximal signed spine on $T$. For this, we provide a characterization of the adjacent linear orders on $V$ in the same fiber of $\kappa$. Two linear orders $\prec$ and $\prec'$ on $V$ are *adjacent* if they only differ by the order of two consecutive elements $u$ and $v$, say for instance $u \prec v$ while $v \prec' u$. In other words, the cones $C(\prec)$ and $C(\prec')$ are adjacent in the braid fan $\mathcal{B}\mathcal{F}(V)$ and separated by the hyperplane $\{\mathbf{x} \in \mathbb{H} \mid x_u = x_v\}$. We then say that two adjacent linear orders $\prec$ and $\prec'$ on $V$ are *T-congruent* if there is a vertex $w$ in between $u$ and $v$ in the ground tree $T$ such that $w \in V^-$ and $u \prec v \prec w$, or $w \in V^+$ and $w \prec u \prec v$.
**Proposition 23** Two adjacent linear orders ≺ and ≺' on V are T-congruent if and only if $κ() = κ(«')$.

**Example 24 (Signed paths)** When T is a signed path, the T-congruence is a type A Cambrian congruence defined by N. Reading in [Rea06]. In particular, if T has only negative signs, the T-congruence is the sylvester congruence [HNT02].

# 5 Signed tree associahedra

In this section, we construct a polytope whose normal fan is the spine fan $\mathcal{F}(T)$ constructed in the previous section. It therefore provides a polytopal realization of the signed nested complex on a tree T that we call signed tree associahedron and denote by Asso(T). It generalizes on the one hand the graph associahedra for trees [CD06, Dev09, Pos09] and on the other hand the various realizations of the associahedron by C. Hohlweg and C. Lange in [HL07], using ideas from [LP13]. In particular, our signed tree associahedron is obtained from the permutahedron by removing certain well-chosen facets. We therefore study some related geometric properties of these polytopes such as their pairs of parallel facets, their common vertices with the permutahedron, and their isometry classes. Further topics can be found in [Pil13].

## 5.1 Vertex and facet descriptions

Before describing our polytopal realization of the signed spine complex, we recall the vertex and facet descriptions of the permutahedron. The permutahedron $\text{Perm}(V)$ is the polytope obtained as

(i) either the convex hull of the vectors $\mathbf{p}(\sigma) := \sum_{i \in [\nu]} i e_{\sigma(i)} \in \mathbb{R}^V$, for all bijections $\sigma : [\nu] \to V$,

(ii) or the intersection of the hyperplane $\mathbb{H}$ with the half-spaces $\mathbf{H}^\geq(U)$ for $\emptyset \neq U \subseteq V$, where

$$ \mathbf{H}^{\geq}(U) := \left\{ \mathbf{x} \in \mathbb{R}^V \mid \sum_{u \in U} x_u \geq \binom{|U|+1}{2} \right\}. $$

Its normal fan is precisely the braid fan $\mathcal{B}\mathcal{F}(V)$ described in Section 4.1. In particular, its k-dimensional faces correspond equivalently to the surjections from V to $[\nu - k]$, to the ordered partitions of V into $\nu - k$ parts, or to the linear preposets on V of rank $\nu - k$. See Figure 4 (right) for an illustration in dimension 3.

We construct the signed tree associahedron Asso(T), with the following vertex and facet descriptions:

(i) The facets of Asso(T) correspond to the signed building blocks of $\mathcal{B}(T)$. Namely, we associate to a signed building block $B \in \mathcal{B}(T)$ the half-space $\mathbf{H}^\geq(B)$ defined above for the permutahedron.

(ii) The vertices of Asso(T) correspond to the maximal signed nested sets of $\mathcal{N}(T)$ or equivalently to the maximal signed spines on T. Consider a maximal signed spine S on T. Let $\Pi(S)$ denote the set of all (undirected and simple) paths in S, including the trivial paths reduced to a single node. At a node labeled by $v \in V$, the signed spine S has a unique outgoing arc $r_v$ if $v \in V^-$ and a unique incoming arc $r_v$ if $v \in V^+$. We let $\mathbf{a}(S)$ be the point in $\mathbb{R}^V$ whose coordinates are defined by

$$ \mathbf{a}(S)_v = \begin{cases} |\{\pi \in \Pi(S) \mid v \in \pi \text{ and } r_v \notin \pi\}| & \text{if } v \in V^-, \\ \nu + 1 - |\{\pi \in \Pi(S) \mid v \in \pi \text{ and } r_v \notin \pi\}| & \text{if } v \in V^+. \end{cases} $$

For example, the vertices associated to the maximal signed spines S and S' of Figure 2 are given by (2, 10, 1, 14, 1, 1, 7, 10, 7, 2) and (2, 10, 1, 18, 1, 1, 7, 10, 3, 2) respectively.

Our main result is the following statement.
**Theorem 25** The spine fan $\mathcal{F}(T)$ is the normal fan of the signed tree associahedron $\text{Asso}(T)$, defined equivalently as

(i) convex hull of the points $a(S)$ for all maximal signed spines $S$ on $T$,

(ii) intersection of the hyperplane $\mathbb{H}$ with the half-spaces $\mathbb{H}^\geq(B)$ for all signed building blocks $B$ of $T$. Thus, the boundary complex of the polar of $\text{Asso}(T)$ is isomorphic to the signed nested complex $\mathcal{N}(T)$.

**Example 26 (Unsigned trees)** When $T$ has only negative vertices, we obtain a new realization of the tree associahedron different from the constructions of M. Carr and S. Devadoss [CD06, Dev09], A. Postnikov [Pos09], and A. Zelevinsky [Zel06]. The normal fan is the same, but the right hand sides of the inequalities are chosen to coincide with that of the permutahedron.

**Example 27 (Signed paths)** For signed paths, we obtain C. Hohlweg and C. Lange's realizations of the associahedron [HL07], including J.-L. Loday's associahedra [Lod04] for unsigned paths. Their construction and its interpretation in terms of spines [LP13] was the guiding light of this work.

**Example 28 (Tripod)** Figure 5 illustrates the facet and vertex descriptions of the signed tree associahedron $\text{Asso}(\rightarrow)$ on the tripod $\rightarrow$ (with three negative leaves and a positive 3-valent vertex).

<figure><img src="image_5.png" /><figcaption>**Fig. 5:** Vertex and facet descriptions of the signed tree associahedron $\text{Asso}(\rightarrow)$.</figcaption></figure>
## 5.2 Further geometric properties

**PARALLEL FACETS.** We first study the pairs of parallel facets of Asso(T) and the resulting parallelepiped.

**Proposition 29** Given any edge e of T, the vertex sets of the two connected components of T \ {e} form complementary signed building blocks of B(T), and therefore define two opposite parallel facets of Asso(T). Moreover, these are the only pairs of parallel facets of Asso(T).

Note that the pairs of parallel facets of Asso(T) do not depend on the signs of T, but only on its underlying unsigned tree. We consider the *parallelepiped* Para(T) defined by the $v - 1$ pairs of parallel facets of Asso(T). The next statement asserts that Para(T) is a dilated graphical zonotope of T.

**Proposition 30** *The parallelepiped Para(T) defined by the $v - 1$ pairs of parallel facets of Asso(T) is the Minkowski sum*

$$ \mathrm{Para}(T) = \sum_{u-v \text{ in } T} \pi(u-v) \cdot [e_u, e_v], $$

where $\pi(u-v)$ denotes the number of paths in T containing the edge $u-v$ of T.

The following statements are direct consequences of Proposition 29.

**Corollary 31** A vertex $v \in V$ is a leaf of T if and only if $\{v\}$ and $V \setminus \{v\}$ are both in $B(T)$.

**Corollary 32** *Except the signs of its leaves, the signed ground tree T can be reconstructed from its signed building set B(T).*

**MATRIOCHKA POLYTOPES.** The permutahedron Perm(V), the signed tree associahedron Asso(T), and the parallelepiped Para(V) are nested polytopes, meaning that $\mathrm{Perm}(V) \subset \mathrm{Asso}(T) \subset \mathrm{Para}(T)$.

**Example 33 (Tripod)** Figure 6 represents the polytopes $\mathrm{Perm}([4]) \subset \mathrm{Asso}(\rightarrow) \subset \mathrm{Para}(\rightarrow)$, where $\rightarrow$ is the tripod with three negative leaves and a positive 3-valent vertex (see Example 28). Their common faces are shaded, and their common vertices are marked with bicolored disks.

<figure><img src="image_6.png" /><figcaption>**Fig. 6:** The permutahedron $\mathrm{Perm}([4])$, the signed tree associahedron $\mathrm{Asso}(\rightarrow)$, and the parallelepiped $\mathrm{Para}(\rightarrow)$.</figcaption></figure>

**NORMAL FANS.** The inclusions $\mathrm{Perm}(V) \subset \mathrm{Asso}(T) \subset \mathrm{Para}(T)$ reflect on their normal fans. Indeed

(i) maximal cones of the normal fan of $\mathrm{Perm}(V)$ correspond to linear orders on V,

(ii) maximal cones of the normal fan of $\mathrm{Asso}(T)$ correspond to maximal signed spines on T,

(iii) maximal cones of the normal fan of $\mathrm{Para}(T)$ correspond to orientations of T.
We have seen in Section 4.3 that the normal fan of $\text{Perm}(V)$ refines that of $\text{Asso}(T)$, thus defining a surjection $\kappa$ from the linear orders on $V$ to the maximal signed spines on $T$. The fiber of a maximal signed spine $S$ is the set of all linear extensions of the transitive closure of $S$. Similarly, the normal fan of $\text{Perm}(V)$ clearly refines that of $\text{Para}(T)$, thus defining a surjection $\mu$ from the linear orders on $V$ to the orientations of $T$. Finally, the next lemma ensures that the normal fan of $\text{Asso}(T)$ refines that of $\text{Para}(T)$.

**Lemma 34** For any edge $u-v$ of $T$ and any maximal spine $S$ of $T$, there is an oriented path in $S$ either from $u$ to $v$ or from $v$ to $u$.

This defines a surjection $\lambda$ from the maximal signed spines on $T$ to the orientations of $T$. To obtain the orientation $\lambda(S)$ corresponding to a maximal signed spine $S$ of $T$, we just orient each edge $u-v$ of $T$ according to the orientation of the unique path between $u$ and $v$ in $S$.

**COMMON VERTICES.** Next, we characterize the common vertices of $\text{Perm}(V) \subset \text{Asso}(T) \subset \text{Para}(T)$.

**Proposition 35** The common vertices of the associahedron $\text{Asso}(T)$ with the parallelepiped $\text{Para}(T)$ are precisely the vertices $\mathfrak{a}(S)$ where $S$ is any orientation of the tree $T$ such that each negative vertex has outdegree at most one while each positive vertex has indegree at most one.

**Proposition 36** Consider a maximal signed spine $S$ on $T$, and a linear order $\prec$ with $\sigma : [\nu] \to V$ such that $\sigma(1) \prec \sigma(2) \prec \cdots \prec \sigma(\nu)$. The following assertions are equivalent:

(i) the vertex $\mathfrak{a}(S)$ of $\text{Asso}(T)$ coincides with the vertex $\mathfrak{p}(\sigma)$ of $\text{Perm}(V)$,

(ii) the normal cone $\text{C}(S)$ of $\text{Asso}(T)$ coincides with the normal cone $\text{C}(\prec)$ of $\text{Perm}(V)$.

(iii) the fiber of $S$ under the surjective map $\kappa$ is the singleton $\kappa^{-1}(S) = \{\prec\}$,

(iv) the spine $S$ is a directed path whose transitive closure is $\prec$,

Following [HLT11], we say that $S$ and $\prec$ are T-singletons if these conditions are fullfiled.

**Corollary 37** The three polytopes $\text{Perm}(V) \subset \text{Asso}(T) \subset \text{Para}(T)$ have two common vertices if $T$ is a signed path and none otherwise.

The next proposition asserts that the T-singletons of the signed tree associahedron $\text{Asso}(T)$ completely determine its facets, and thus its geometry. This property, observed by C. Hohlweg and C. Lange for their path associahedra [HL07], was the heart of the extension of their results to all Coxeter groups [HLT11].

**Proposition 38** Any linear preposet on $V$ whose Hasse diagram is a signed spine on $T$ admits a linear extension whose Hasse diagram is also a signed spine on $T$. In other words, a face of $\text{Asso}(T)$ contains a T-singleton if and only if its corresponding signed spine is a directed path. In particular, any facet of $\text{Asso}(T)$ contains a T-singleton.

**ISOMETRY CLASSES.** We say that two signed trees $T$ and $T'$ on signed ground sets $V$ and $V'$ respectively are *isomorphic* (resp. *anti-isomorphic*) if there is a bijection $\theta : V \to V'$ such that, for all $u, v \in V$,

* $u-v$ is an edge in $T$ if and only if $\theta(u)-\theta(v)$ is an edge in $T'$, and

* the signs of $u$ and $\theta(u)$ coincide (resp. are opposite).

We say that $T$ and $T'$ are isomorphic (resp. anti-isomorphic) *up to the signs of their leaves* if Condition (ii) holds for internal vertices of $T$. The following statement is similar to that of [BHLT10] to characterize the isometry classes of the generalized associahedra of [HLT11].

**Proposition 39** Let $T$ and $T'$ be two signed trees on signed ground sets $V$ and $V'$ respectively. Then the signed tree associahedra $\text{Asso}(T)$ and $\text{Asso}(T')$ are isometric if and only if the signed ground trees $T$ and $T'$ are isomorphic or anti-isomorphic, up to the signs of their leaves.
References

[BHLT10] N. Bergeron, C. Hohlweg, C. Lange, and H. Thomas. Isometry classes of generalized associahedra. *Sém. Lothar. Combin.*, 61A:Art. B61Aa, 13, 2009/10.

[CD06] M. Carr and S. Devadoss. Coxeter complexes and graph-associahedra. *Topology Appl.*, 153(12):2155-2168, 2006.

[Dev09] S. Devadoss. A realization of graph associahedra. *Discrete Math.*, 309(1):271-276, 2009.

[FS05] E.-M. Feichtner and B. Sturmfels. Matroid polytopes, nested sets and Bergman fans. *Port. Math. (N.S.)*, 62(4):437-468, 2005.

[HL07] C. Hohlweg and C. Lange. Realizations of the associahedron and cyclohedron. *Discrete Comput. Geom.*, 37(4):517-543, 2007.

[HLT11] C. Hohlweg, C. Lange, and H. Thomas. Permutahedra and generalized associahedra. *Adv. Math.*, 226(1):608-640, 2011.

[HNT02] F. Hivert, J.-C. Novelli, and J.-Y. Thibon. Un analogue du monoïde plaxique pour les arbres binaires de recherche. *C. R. Math. Acad. Sci. Paris*, 335(7):577-580, 2002.

[IO13] K. Igusa and J. Ostroff. Mixed cobinary trees. Preprint, arXiv:1307.3587, 2013.

[Lod04] J.-L. Loday. Realization of the Stasheff polytope. *Arch. Math. (Basel)*, 83(3):267-278, 2004.

[LP13] C. Lange and V. Pilaud. Using spines to revisit a construction of the associahedron. Preprint, arXiv:1307.4391, 2013.

[MHPS12] F. Müller-Hoissen, J. M. Pallo, and J. Stasheff, editors. *Associahedra, Tamari Lattices and Related Structures. Tamari Memorial Festschrift*, volume 299 of *Progress in Mathematics*. Birkhäuser, Basel, 2012.

[Pil13] V. Pilaud. Signed tree associahedra. Preprint, arXiv:1309.5222, 2013.

[Pos09] A. Postnikov. Permutohedra, associahedra, and beyond. *Int. Math. Res. Not. IMRN*, 6:1026-1106, 2009.

[PRW08] A. Postnikov, V. Reiner, and L. Williams. Faces of generalized permutohedra. *Doc. Math.*, 13:207-273, 2008.

[Rea06] N. Reading. Cambrian lattices. *Adv. Math.*, 205(2):313-353, 2006.

[RS09] N. Reading and D. Speyer. Cambrian fans. *J. Eur. Math. Soc. (JEMS)*, 11(2):407-447, 2009.

[Sta63] J. Stasheff. Homotopy associativity of H-spaces I, II. *Trans. Amer. Math. Soc.*, 108(2):293-312, 1963.

[Zel06] A. Zelevinsky. Nested complexes and their polyhedral realizations. *Pure Appl. Math. Q.*, 2(3):655-671, 2006.