# Fan realizations of type A subword complexes and multi-associahedra of rank 3

Nantel Bergeron, Cesar Ceballos, Jean-Philippe Labbé

► To cite this version:

Nantel Bergeron, Cesar Ceballos, Jean-Philippe Labbé. Fan realizations of type A subword complexes and multi-associahedra of rank 3. 27th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2015), Jul 2015, Daejeon, South Korea. pp.429-440, 10.46298/dmtcs.2512 . hal-01337805

HAL Id: hal-01337805

https://hal.science/hal-01337805

Submitted on 27 Jun 2016

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Fan realizations of type A subword complexes and multi-associahedra of rank 3

Nantel Bergeron<fnref n="1" />† and Cesar Ceballos<fnref n="1" />‡ and Jean-Philippe Labbé<fnref n="2" />§

**Abstract.** We present complete simplicial fan realizations of any spherical subword complex of type $A_n$ for $n \le 3$. This provides complete simplicial fan realizations of simplicial multi-associahedra $\Delta_{2k+4,k}$, whose facets are in correspondence with $k$-triangulations of a convex $(2k+4)$-gon. This solves the first open case of the problem of finding fan realizations where polytopality is not known. The techniques presented in this paper work for all finite Coxeter groups and we hope that they will be useful to construct fans realizing subword complexes in general. In particular, we present fan realizations of two previously unknown cases of subword complexes of type $A_4$, namely the multi-associahedra $\Delta_{9,2}$ and $\Delta_{11,3}$.

**Résumé.** Nous construisons des éventails simpliciaux complets ayant la combinatoire des complexes de sous-mots de type $A_n$ pour $n \le 3$. Par conséquent, nous obtenons des constructions d'éventails des multi-associaèdres $\Delta_{2k+4,k}$, dont les facettes correspondent aux $k$-triangulations d'un $(2k+4)$-gone. Cette construction confirme l'existence d'éventails ayant la combinatoire du multi-associaèdres pour une famille dont la polytopalité n'est pas confirmée. Les techniques utilisées fonctionnent pour tous les groupes de Coxeter et nous espérons qu'elles seront utiles afin de construire des éventails réalisant les complexes de sous-mots en général. En particulier, nous présentons des éventails pour deux complexes de sous-mots de type $A_4$ dont l'existence était inconnue: les multi-associaèdres $\Delta_{9,2}$ et $\Delta_{11,3}$.

**Keywords:** simplicial fans, multiassociahedra, subword complex, Gale duality, realization space.

## 1 Introduction

Subword complexes are simplicial complexes introduced by Knutson and Miller [KM04] motivated from the study of Gröbner geometry of Schubert varieties [KM05]. They proved that any subword complex is either a topological ball or sphere [KM04, Corollary 3.8], and asked the question of whether every spherical subword complex can be realized as the boundary complex of a polytope [KM04, Question 6.4]. The

<footnote n="1">¹Fields Institute, York University, Toronto, ON, Canada</footnote>

<footnote n="2">²Einstein Institute of Mathematics, Hebrew University of Jerusalem, Jerusalem, Israel</footnote>

<footnote>†Email: bergeron@mathstat.yorku.ca. Partially supported by NSERC.</footnote>

<footnote>‡Email: ceballos@mathstat.yorku.ca. Supported by the government of Canada through a Banting Postdoctoral Fellowship and by a York University research grant.</footnote>

<footnote>§Email: labbe@math.huji.ac.il. Supported by a FQRNT Doctoral scholarship and SFB Transregio "Discretization in Geometry and Dynamics" (TRR 109).</footnote>
answer to this question has been verified to be positive only for a few cases, which include interesting fam-
ilies of polytopes such as all even dimensional cyclic polytopes [CLS14], the duals of c-generalized asso-
ciahedra [CLS14], the pseudotriangulation polytope of any planar point set in general position [RSS03],
and the brick polytopes of “root-independent subword complexes” [PS12, PS15]. Another family of
closely related simplicial complexes is the family of multi-associahedra. Given any two positive integers
$k \ge 1$ and $\ell \ge 2k + 1$, the (simplicial) multi-associahedron $\Delta_{\ell,k}$ is a simplicial complex whose facets
correspond to $k$-triangulations of a convex $\ell$-gon [Jon05]. This simplicial complex is conjectured to be
realizable as the boundary complex of a polytope [Jon05, Section 1.2]. The only cases for which this
conjecture has been verified are summarized in Table 1.

<table><caption>**Tab. 1:** Known results about polytopality of multi-associahedra.</caption>
  <thead>
    <tr>
      <th>&Delta;<sub>&ell;,k</sub></th>
      <th>Realizable as a</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <td>k = 1</td>
      <td>dual of a classical associahedron [CSZ14, MHPS12]</td>
    </tr>
    <tr>
      <td>&ell; = 2k + 1</td>
      <td>single vertex</td>
    </tr>
    <tr>
      <td>&ell; = 2k + 2</td>
      <td>simplex</td>
    </tr>
    <tr>
      <td>&ell; = 2k + 3</td>
      <td>cyclic polytope [PS09, CLS14]</td>
    </tr>
    <tr>
      <td>&ell; = 2k + 4</td>
      <td>complete simplicial fan (<i>this paper</i>)</td>
    </tr>
    <tr>
      <td>&Delta;<sub>8,2</sub></td>
      <td>6-dimensional polytope [BP09, Ceb12] (<i>this paper</i>)</td>
    </tr>
    <tr>
      <td>&Delta;<sub>9,2</sub></td>
      <td>complete simplicial fan (<i>this paper</i>)</td>
    </tr>
    <tr>
      <td>&Delta;<sub>11,3</sub></td>
      <td>complete simplicial fan (<i>this paper</i>)</td>
    </tr>
  </tbody>
</table>

Subword complexes and multi-associahedra turn out to be quite related: every multi-associahedron can
be obtained as a well chosen subword complex of type A [PP12, Stu11], see also [SS12]. Conversely, the
family of multi-associahedra is universal, in the sense that every spherical subword complex of type A
can be obtained as the link of a face in a multi-associahedron [PS12, Proposition 5.6], see also [CLS14,
Theorem 2.15]. The relation between these two families of simplicial complexes has been extended to
arbitrary finite Coxeter groups in [CLS14].

In this extended abstract, we present complete simplicial fan realizations for any spherical subword
complex of type $A_n$ for $n \le 3$. This is particularly interesting for the case $n = 3$, where the answer to
the question of polytopality is not known. In particular, we obtain complete simplicial fan realizations of
multi-associahedra $\Delta_{\ell,k}$ for $\ell \le 2k + 4$, which solves the previously unknown case when $\ell = 2k + 4$.
Our constructions also lead to a large connected component of the fan realization space in each case,
see Section 5. It is also natural to ask whether the complete simplicial fans constructed here are normal
fans of polytopes. Although it is often true for $k \le 2$, we do not know if any of our fan realizations
for $\Delta_{10,3}$ is the normal fan of a polytope. The multi-associahedron $\Delta_{10,3}$ is a 3-neighborly simplicial
complex of dimension 8 with f-vector $(1, 15, 105, 455, 1320, 2607, 3465, 2970, 1485, 330)$. We tested
144139 different fans realizing it among the infinitely many produced by our construction, and none
of them is the normal fan of a polytope, see Table 4. Nevertheless, the polytopality question of multi-
associahedra remains open in general, see Section 4 for more details.

Our construction of the fans can be applied for any subword complex of type $A_n$. Although it does
not produce the right fans for $n \ge 4$, it seems to be close to a valid construction, at least for small values
of $k$ and $n$. We argue this fact in Section 6, where we apply a slight modification to our construction to
produce fan realizations of two previously unknown cases of subword complexes of type $A_4$, namely the
multi-associahedra $\Delta_{9,2}$ and $\Delta_{11,3}$. We remark that these two cases are far from trivial. In particular, they are intractable with computational methods previously used in the literature [BP09, Ceb12]. The corresponding $f$-vectors are presented in Table 2. Interestingly, we show that the two fans we present for $\Delta_{9,2}$ and $\Delta_{11,3}$ can not be obtained as the normal fan of a polytope.

<table><caption>**Tab. 2:** $f$-vectors of two multi-associahedra of type $A_4$.</caption><thead><tr><th>Δ<sub>ℓ,k</sub></th><th>neighborliness</th><th>dim.</th><th>f-vector</th></tr></thead><tbody><tr><td>Δ<sub>9,2</sub></td><td>2-neighborly</td><td>7</td><td>(1, 18, 153, 732, 2115, 3762, 4026, 2376, 594)</td></tr><tr><td>Δ<sub>11,3</sub></td><td>3-neighborly</td><td>11</td><td>(1, 22, 231, 1540, 7150, 23958, 58751, 105534, 137280, 125840, 77077, 28314, 4719)</td></tr></tbody></table>

## 2 Definitions and main results

Let $(W, S)$ be a finite Coxeter system. Let $Q = (q_1, \dots, q_r)$ be a word in the generators $S$ and $\pi \in W$ be an element of the group.

**Definition 2.1 (Knutson–Miller [KM04])** The subword complex $\mathcal{SC}(Q, \pi)$ is the simplicial complex whose faces are subsets $I \subset [r]$ such that the subword of $Q$ with positions at $[r] \setminus I$ contains a reduced expression for $\pi$.

As mentioned above, a subword complex is either a ball or sphere. It was proven in [CLS14, Theorem 3.7] that every spherical subword complex is isomorphic to a subword complex of the form $\mathcal{SC}(Q, w_o)$, where $w_o$ is the longest element of the group. Therefore, we restrict our study to subword complexes of this form and write $\mathcal{SC}(Q)$ for simplicity. We denote by $N := \ell(w_o)$ the length of $w_o$.

**Definition 2.2** Given a word $Q$ and a matrix $M \in \mathbb{R}^{(r-N) \times r}$, we define a natural collection of cones $\mathcal{F}_{Q,M}$ in $\mathbb{R}^{r-N}$. Its rays are given by the column vectors of $M$ and its cones are spanned by the columns corresponding to faces of subword complex $\mathcal{SC}(Q)$.

The techniques in this paper work for arbitrary finite Coxeter groups. However, part of our main results are devoted to the Coxeter groups of type $A$. Let $W$ be a Coxeter group of type $A$ generated by the set $S = \{s_1, \dots, s_n\}$ of simple transpositions $s_i = (i \ i+1)$. Let $\Delta$ be the corresponding set of simple roots and $\Phi = W \cdot \Delta = \Phi^+ \sqcup \Phi^-$ be the set of roots partitioned into positive and negative roots respectively. Let $c = (s_1, \dots, s_n)$ be a Coxeter element, and $P_m = c^m = (p_1, \dots, p_{mn})$ be a sufficiently long word that contains $Q$ as a subword. The main ingredient in our construction is a counting matrix $D_{c,m}$, whose entries count the number of reduced expressions of $c$ in $P_m$ using the letter $p_i$, after restricting to standard parabolic subgroups.

**Definition 2.3** The counting matrix $D_{c,m}$ is a $(N \times mn)$-matrix whose rows correspond to positive roots and columns to the positions $1 \le j \le mn$ of the letters of $P_m = c^m = (p_1, \dots, p_{mn})$. Given $\alpha \in \Phi^+$ and $1 \le j \le mn$, denote by $S_\alpha \subset S$ the subset of generators whose corresponding simple roots are used in the unique decomposition of the root $\alpha$ in the basis $\Delta$ and by $c_\alpha$ the restriction of $c$ to the generators in $S_\alpha$. The entry $d_{\alpha,j}$ of $D_{c,m}$ is the number of reduced expressions of $c_\alpha$ in $P_m$ (copies of $c_\alpha$ up to commutations) using the letter $p_j$. In particular, if $p_j \notin S_\alpha$, then $d_{\alpha,j} = 0$.
For any embedding $\varphi : Q \to c^m$ of $Q$ into a sufficiently long word $P_m = c^m$ we construct, in Theorem 2.6, a complete simplicial fan realization of the spherical subword complex $\mathcal{SC}(Q)$. This embedding can be thought as a map $\varphi : [r] \to [mn]$ from positions in $Q$ to positions in $P_m$.

**Definition 2.4** The restricted matrix $D_\varphi$ is the restriction of $D_{c,m}$ to the columns $\varphi(1), \dots, \varphi(r)$ corresponding to the positions of the letters of $Q$ embedded in $c^m$.

**Example 2.5** Let $P_4 = c^4 = (\mathfrak{s}_1, \mathfrak{s}_2, s_1, \mathfrak{s}_2, s_2, \mathfrak{s}_1, s_2, \mathfrak{s}_2)$ be a word of type $A_2$. The counting matrix $D_{c,4}$ is given below, where the rows correspond to the positive roots $\{\alpha_1, \alpha_1 + \alpha_2, \alpha_2\}$ in this order. If we take $Q$ corresponding to the underlined letters embedded in $P_4$, the dual restricted matrix $D_\varphi$ is the restriction of $D_{c,4}$ to the corresponding columns.

$$D_{c,4} = \begin{pmatrix} 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \\ 4 & 1 & 3 & 2 & 2 & 3 & 1 & 4 \\ 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \end{pmatrix} \qquad D_\varphi = \begin{pmatrix} 1 & 0 & 0 & 1 & 1 \\ 4 & 1 & 2 & 2 & 1 \\ 0 & 1 & 1 & 0 & 0 \end{pmatrix}$$

Given a full rank matrix $D$, we say that $M$ is a *Gale dual matrix* of $D$ if the rows of $M$ form a basis for the kernel of $D$, see [DLRS10, Definition 4.1.35]. This dual matrix is determined up to linear transformation of its rows. Let $M_\varphi$ be a Gale dual matrix of $D_\varphi$.

**Theorem 2.6** Let $\mathcal{SC}(Q)$ be a spherical subword complex of type $A_n$ with $n \le 3$, and $\varphi$ be an embedding of $Q$ into $c^m$. The fan $\mathcal{F}_{Q,M_\varphi}$ is a complete simplicial fan realization of $\mathcal{SC}(Q)$.

This result provides infinitely many complete simplicial fan realizations of any spherical subword complex of type $A_n$ with $n \le 3$. In the particular cases where the word $Q = c^m$ is naturally embedded into itself we get explicit realizations. In the corollaries below, the entries of the matrices depend on the functions $S(i) = i^2$ and $T(i) = i(i+1)/2$.

**Corollary 2.7** Let $c = (s_2, s_1, s_3)$ be a bipartite Coxeter element of type $A_3$ and $Q = c^m$, with $m \ge 3$. The fan $\mathcal{F}_{Q,M_{213,m}}$ is a complete simplicial fan realization of $\mathcal{SC}(Q)$ for the matrix $M_{213,m}$ below.

$$M_{213,m} := \left( \begin{array}{c} B_{213,m-2} \\ \vdots \\ B_{213,1} \end{array} \right)_{(3m-6)\times(3m)} \qquad B_{213,i} := \left( \begin{array}{ccc} S(i+1) & -T(i) & -T(i) \\ 2T(i) & -T(i-1)+1 & -T(i) \\ 2T(i) & -T(i) & -T(i-1)+1 \\ -S(i+1)+1 & T(i) & T(i) \\ -2T(i) & T(i-1) & T(i) \\ -2T(i) & T(i) & T(i-1) \end{array} \right)$$

A similar corollary holds for the Coxeter element $c = (s_1, s_2, s_3)$.

**Example 2.8 (3-dimensional associahedron)** Let $c = (s_2, s_1, s_3)$ be a bipartite Coxeter element of type $A_3$ and $Q = c^3$. The subword complex $\mathcal{SC}(Q)$ is isomorphic to a 3-dimensional simplicial associahedron. It can be realized as a complete simplicial fan $\mathcal{F}_{Q,M_{213,3}}$ where

$$M_{213,3} = \begin{pmatrix} -1 & 0 & 0 & 4 & 2 & 2 & -3 & -2 & -2 \\ 0 & -1 & 0 & -1 & 1 & -1 & 1 & 0 & 1 \\ 0 & 0 & -1 & -1 & -1 & 1 & 1 & 1 & 0 \end{pmatrix}$$

This fan is the normal fan of a polytope. Figure 1 illustrates eight polytopal realizations associated to appropriate words $Q$ and different choices of embeddings $\varphi$ in Theorem 2.6.
<figure><img src="image_2.png" /><figcaption>**Fig. 1:** Eight different polytopal realizations of the 3-dimensional associahedron using embeddings of a word $Q$ into some $c^m$ for the Coxeter elements $c = s_1s_2s_3$ and $c = s_2s_1s_3$</figcaption></figure>

Corollary 2.7 can also be restated in terms of multi-associahedra. Before giving a precise statement let us recall some basic definitions. Let $k \ge 1$ and $\ell \ge 2k + 1$ be two positive integers. We say that a set of $k + 1$ diagonals of a convex $\ell$-gon forms a $(k+1)$-crossing if all the diagonals in this set are pairwise crossing. A diagonal is called *k-relevant* if it is contained in some $(k+1)$-crossing, that is, if there are at least $k$ vertices of the $\ell$-gon on each side of the diagonal. The simplicial multi-associahedron $\Delta_{\ell,k}$ is the simplicial complex of $(k+1)$-crossing-free sets of $k$-relevant diagonals of a convex $\ell$-gon. We are particularly interested in the case $\ell = 2k + 4$, where the polytopality conjecture is still open. In this case, there are exactly $3k + 6$ $k$-relevant diagonals, which are in correspondence with the columns of the matrix $M_{213,k+2}$ as follows: cyclically label the vertices of the $\ell$-gon from 1 up to $\ell$. The first $k$-relevant diagonal in lexicographic order corresponds to the last column of $M_{213,k+2}$, the other $k$-relevant diagonals correspond to the other columns in the order they appear in lexicographic order, see Example 2.10. Let $\mathcal{F}_k$ be the simplicial fan in $\mathbb{R}^{3k}$ whose rays are the column vectors of $M_{213,k+2}$, and whose cones are spanned by the column vectors corresponding to faces of $\Delta_{2k+4,k}$. Using this terminology, Corollary 2.7 can be read as follows.

**Corollary 2.9** The fan $\mathcal{F}_k$ is a complete simplicial fan realization of the multi-associahedron $\Delta_{2k+4,k}$.

**Example 2.10 (Multi-associahedron $\Delta_{10,3}$)** The multi-associahedron $\Delta_{10,3}$ can be realized as the complete simplicial fan $\mathcal{F}_3$. The rays are the column vectors of the matrix $M_{213,5}$ below, and the cones are spanned by the column vectors corresponding to faces of $\Delta_{10,3}$. The pairs of numbers on top of the matrix are the 3-relevant diagonals of the 10-gon associated to each of the columns of the matrix.
$$
M_{213,5} =
\begin{pmatrix}
1,6 & 1,7 & 2,6 & 2,7 & 2,8 & 3,7 & 3,8 & 3,9 & 4,8 & 4,9 & 4,10 & 5,9 & 5,10 & 6,10 & 1,5 \\
-1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 16 & 12 & 12 & -15 & -12 & -12 \\
0 & -1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & -6 & -2 & -6 & 6 & 3 & 6 \\
0 & 0 & -1 & 0 & 0 & 0 & 0 & 0 & 0 & -6 & -6 & -2 & 6 & 6 & 3 \\
0 & 0 & 0 & -1 & 0 & 0 & 0 & 0 & 0 & 9 & 6 & 6 & -8 & -6 & -6 \\
0 & 0 & 0 & 0 & -1 & 0 & 0 & 0 & 0 & -3 & 0 & -3 & 3 & 1 & 3 \\
0 & 0 & 0 & 0 & 0 & -1 & 0 & 0 & 0 & -3 & -3 & 0 & 3 & 3 & 1 \\
0 & 0 & 0 & 0 & 0 & 0 & -1 & 0 & 0 & 4 & 2 & 2 & -3 & -2 & -2 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & -1 & 0 & -1 & 1 & -1 & 1 & 0 & 1 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & -1 & -1 & -1 & 1 & 1 & 1 & 0
\end{pmatrix}
$$

Remarkably, this fan can not be obtained as the normal fan of a polytope. Even more surprising, using different embeddings of an appropriate word into $c^m$, we tested more than a hundred thousand different fans realizing $\Delta_{10,3}$ and none of them turned out to be the normal fan of a polytope, see Table 4. We refer to Section 4 for more details.

3 The sign function and Coxeter signature matrices

Theorem 2.6 relies on a reformulation of the problem in terms of two notions related to Coxeter groups: a *sign function* on reduced expressions of an element and a *Coxeter signature matrix*, see Theorem 3.6.

3.1 Graph of reduced expressions of w and sign function

Given a finite Coxeter group $W$ and an element $w \in W$, we consider the graph $G(w)$ of reduced expressions of $w$ connected by braid relations, see [RR13, Hum92]. Figure 2 illustrates an example of the graph $G(w_0)$ for the symmetric group $W = S_4$. The 16 vertices are labeled by the subscript sequence of the 16 reduced expressions of $w_0$. For example, 123121 represents the reduced expression $s_1s_2s_3s_1s_2s_1$. We say that the pairs $\{i, j\}$ and $\{i', j'\}$ are in the same *conjugate class* if $s_{i'} = w^{-1}s_iw$ and $s_{j'} = w^{-1}s_jw$ for some $w \in W$.

**Proposition 3.1** Let $W$ be a finite Coxeter group and $w$ be an element in $W$. Then, any loop in the graph $G(w)$ contains an even number of edges labeled by pairs in the conjugate class of $\{i, j\}$ (corresponding to a braid relation $m_{ij}$) for any fixed pair $\{i, j\}$. In particular

1. Any loop in $G(w)$ contains an even number of edges.

2. Any loop in $G(w)$ contains an even number of edges corresponding to even braid relations.

3. Any loop in $G(w)$ contains an even number of edges corresponding to odd braid relations.

**Remark 3.2** Taking the conjugate classes of pairs $\{i, j\}$ is necessary for the result to be true. Consider the reduced expression $s_1s_2s_1s_4$ in $A_4$. The sequence of braid moves

$$
\begin{align*}
s_1 s_2 s_1 s_4 \xrightarrow{14} s_1 s_2 s_4 s_1 \xrightarrow{24} s_1 s_4 s_2 s_1 \xrightarrow{14} s_4 s_1 s_2 s_1 \xrightarrow{12} s_4 s_2 s_1 s_2 \\
\phantom{s_1 s_2 s_1 s_4} \xrightarrow{24} s_2 s_4 s_1 s_2 \xrightarrow{14} s_2 s_1 s_4 s_2 \xrightarrow{24} s_2 s_1 s_2 s_4 \xrightarrow{12} s_1 s_2 s_1 s_4
\end{align*}
$$

is a loop in the graph of $G(w)$ that contains three braid relations $\{1, 4\}$, not an even number. But if we consider both $\{1, 4\}$ and $\{2, 4\}$, then we get six braid relations of that type, an even number.
Part 2 of this proposition allows the following sign function to be well-defined.

**Definition 3.3** The sign function on reduced expressions of $w_◦$ is a map

$$ \text{sign} : \{\text{reduced expressions of } w_◦\} \to \{1, -1\} $$

such that if $w, w'$ are two reduced expressions of $w_◦$ connected by a braid move $m_{ij}$, then

$$ \text{sign}(w') = (-1)^{m_{ij}-1} \cdot \text{sign}(w). \qquad (1) $$

Since the graph of reduced expressions of $w_◦$ is connected [Tit69], this function is unique up to global multiplication by $-1$. Two reduced expressions connected by an odd braid move have the same sign, while two connected by an even braid move have opposite signs. In the case of type $A_n$, this sign function also appears in a connection between scattering amplitudes in physics and the positive Grassmannian [AHBC$^+$14]. More precisely, the authors sign function arising from the case of the Grassmannian $G(2, n)$ coincides with the sign function of reduced expressions of $w_◦$ in type $A_n$. Figure 2 illustrates the sign function on reduced expressions of $w_◦$ in type $A_3$.

<figure><img src="image_3.png" /><figcaption>**Fig. 2:** The sign function on reduced expressions of $w_◦$ in type $A_3$: red (thick) edges represent even braid relations (commutations in this case), and blue (thin) edges represent odd braid relations</figcaption></figure>

**Remark 3.4 (Sign function of type $A_n$)** The sign function of type $A_n$ can be easily described in terms of their inversions. Let $w = w_1...w_N$ be a reduced expression of $w_◦$ and $t_1, ..., t_N$ be the corresponding inversions given by $t_k = w_1...w_k...w_1$. Each $t_k$ is a transposition of the form $(i_k, j_k)$. If we replace each $t_k$ by $\min\{i_k, j_k\}$, we obtain a multi-permutation of

$$ \underbrace{111...1}_{n \text{ times}} \underbrace{22...2}_{n-1 \text{ times}} \dots n-1 n-1 n. $$

The sign($w$) is the sign of this multi-permutation. According to personal communication with Alexander Postnikov, the sign of $w$ can be alternatively obtained as the product of the sign of the permutation of inversions of $w$ with $-1$ to the number of higher inversions of $w$.
## 3.2 Coxeter signature matrix

Let $Q = (q_1, \dots, q_r)$ be a word in $S$ containing at least one reduced expression of $w_0$, and let $N = \ell(w_0)$ be the length of the longest element in $W$.

**Definition 3.5 (Coxeter signature matrix)** A matrix $M \in \mathbb{R}^{N \times r}$ is a signature matrix of type $W$ for the pair $(Q, w_0)$ if for every reduced expression $w \subset Q$ of $w_0$,

$$ \mathrm{sign}(w) \cdot \mathrm{det}(w) > 0, \qquad (2) $$

where $\mathrm{det}(w)$ is the determinant of the matrix $M$ restricted to the columns corresponding to $w$, and $\mathrm{sign}(w)$ is the sign function of $w$ according to Definition 3.3.

Consider a full rank matrix $M \in \mathbb{R}^{(r-N) \times r}$ and a Gale dual matrix $M^G \in \mathbb{R}^{N \times r}$, as well as the associated fan $\mathcal{F}_{Q,M}$ from Definition 2.2.

**Theorem 3.6** $\mathcal{F}_{Q,M}$ is a complete simplicial fan realization of $\mathcal{SC}(Q)$ if and only if

(S) $M^G$ is a Coxeter signature matrix for the pair $(Q, w_0)$ (Signature), and

(I) there is a facet of $\mathcal{SC}(Q)$ for which the interior of its associated cone is not intersected by any other cone (Injectivity).

**Proposition 3.7** Let $W$ be a Coxeter group of type $A_n$ with $n \le 3$, let $c$ be a Coxeter element and $Q = c^m$. The counting matrix $D_{c,m}$ is a signature matrix for the pair $(Q, w_0)$.

Proposition 3.7 is proved using explicit computations of the determinants in (2). We remark that it does not hold for $n \ge 4$ and address the problem of finding Coxeter signature matrices in general.

# 4 Polytopality

Following [DLRS10], we say that a fan is *regular* if it is the normal fan of a polytope. One natural question is whether the fans in Theorem 2.6 are regular. The answer is negative in general, most of the fans $\mathcal{F}_{Q,M_\ell}$ are not. We restrict the verification of regularity to the family of multi-associahedra $\Delta_{\ell,k}$, whose facets are in bijection with $k$-triangulations of a convex $\ell$-gon. The multi-associahedron $\Delta_{n+2k+1,k}$ can be obtained as a subword complex $\mathcal{SC}(Q)$ for any word $Q$ equal to $c^k w_0(c)$ up to commutations, where $w_0(c)$ denotes the lexicographically first reduced expression of $w_0$ in $c^\infty$. We refer to [CLS14] for more details on this connection. We used the computer algebra system Sage [S+14] to produce all the words $Q$ satisfying this property and tested regularity of the fans corresponding to embeddings of $Q$ into a longer word $c^m$ for different values of $m$ in types $A_2$ and $A_3$. The results are summarized in Tables 3 and 4. It is surprising to have so many different non-regular fans realizing $\Delta_{10,3}$.

**Remark 4.1** Our computational results reveal that more than a hundred thousand possible fans realizing the multi-associahedron $\Delta_{10,3}$ are not the normal fan of a polytope. We do not know if there are embeddings into longer words $c^m$ for which the fan is regular. We found out that the fans associated to the subword complex $\mathrm{Obs}(A_3) := \mathcal{SC}(1212321212)$ embedded in words $c^m$ with $m \le 10$ and $c$ any Coxeter element are not regular. This obstruction is minimal: removing any letter to $\mathrm{Obs}(A_3)$ yields a regular complete fan. The subword complex $\mathrm{Obs}(A_3)$ appears to be a possible candidate to disprove the polytopality conjecture for subword complexes. The f-vector of $\mathrm{Obs}(A_3)$ is $(1, 9, 30, 42, 21)$. As it turns out,
<table><caption>**Tab. 3:** Results of regularity tests on complete simplicial fans of type $A_2$.</caption><thead><tr><th>Δ<sub>2k+3,k</sub></th><th>A<sub>2</sub></th><th>m</th><th>Regular fans</th><th>Non-regular fans</th></tr></thead><tbody><tr><td>Δ<sub>5,1</sub></td><td>k = 1</td><td>m ≤ 11</td><td>6006</td><td>0</td></tr><tr><td>Δ<sub>7,2</sub></td><td>k = 2</td><td>m ≤ 11</td><td>12870</td><td>0</td></tr><tr><td>Δ<sub>9,3</sub></td><td>k = 3</td><td>m ≤ 11</td><td>16016</td><td>0</td></tr><tr><td>Δ<sub>11,4</sub></td><td>k = 4</td><td>m ≤ 11</td><td>12376</td><td>0</td></tr><tr><td>Δ<sub>13,5</sub></td><td>k = 5</td><td>m ≤ 10</td><td>1360</td><td>0</td></tr><tr><td>Δ<sub>15,6</sub></td><td>k = 6</td><td>m ≤ 10</td><td>306</td><td>0</td></tr></tbody></table>

<table><caption>**Tab. 4:** Results of regularity tests on complete simplicial fans of type $A_3$.</caption><thead><tr><th>Δ<sub>2k+4,k</sub></th><th>A<sub>3</sub></th><th>m</th><th>Regular fans</th><th>Non-regular fans</th></tr></thead><tbody><tr><td>Δ<sub>6,1</sub></td><td>k = 1</td><td>m ≤ 12</td><td>1 144 293</td><td>136</td></tr><tr><td>Δ<sub>8,2</sub></td><td>k = 2</td><td>m ≤ 11</td><td>66 293</td><td>743 560</td></tr><tr><td>Δ<sub>10,3</sub></td><td>k = 3</td><td>m ≤ 10</td><td>0</td><td>144 939</td></tr></tbody></table>

the subword complex Obs($A_3$) is polytopal, see [AS76, Table 3]. During FPSAC 2013, Francisco Santos obtained an explicit construction of a 4-dimensional polytope whose boundary complex is Obs($A_3$). We are grateful to him and his great insight.

# 5 Fan realization space

This section presents a large connected component of the fan realization space of spherical subword complexes of type $A_3$. We tested regularity of many fans arising this way and none of them were regular. For a collection of real parameters $a = \{a_i, b_i, c_i\}_{i=1,...,m}$ define the a-counting matrix $D_{123,a}$ as the matrix

$$D_{123,a} = \left( \begin{array}{c|c|c} \tilde{D}_m^a & \dots & \tilde{D}_1^a \end{array} \right)_{6 \times 3m} \qquad \tilde{D}_i^a = \left( \begin{array}{ccc} 1 & 0 & 0 \\ a_i & m-b_i+1 & 0 \\ \binom{a_i+1}{2} & (m-b_i+1)(b_i) & \binom{m-c_i+2}{2} \\ 0 & 1 & 0 \\ 0 & b_i & m-c_i+1 \\ 0 & 0 & 1 \end{array} \right)$$

and denote by $M_{123,a}$ any Gale dual matrix of $D_{123,a}$. We are particularly interested in parameters satisfying the *c-signature inequalities* in Figure 3, for $c = (s_1, s_2, s_3)$.

**Theorem 5.1** Let $c = (s_1, s_2, s_3)$ be a Coxeter element of type $A_3$ and $Q = c^m$, with $m \ge 3$. For any choice of real parameters $a = \{a_i, b_i, c_i\}_{i=1,...,m}$ satisfying the *c-signature inequalities* in Figure 3, the fan $\mathcal{F}_{Q,M_{123,a}}$ is a complete fan realizing $\mathcal{SC}(Q)$.

A similar result is valid for the bipartite Coxeter element $c = (s_2, s_1, s_3)$.
<figure><img src="image_4.png" /><figcaption>**Fig. 3:** Signature inequalities for $c = (s_1, s_2, s_3)$ in type $A_3$. The dashed shapes on the right show an example of the parameters involved in the fourth equation</figcaption></figure>

# 6 Multi-associahedra of Type $A_4$

Let $c = (s_2, s_4, s_1, s_3)$ be a bipartite Coxeter element of type $A_4$ and $Q = c^k w_\circ(c)$. For this particular Coxeter element $w_\circ(c) = (2, 4, 1, 3, 2, 4, 1, 3, 2, 4)$. The subword complex $\mathcal{SC}(Q)$ is isomorphic to the multi-associahedron $\Delta_{2k+5,k}$. We refer to [CLS14, Section 2.4] for an explicit bijection between positions in the word $Q$ and $k$-relevant diagonals in the polygon. We tested if the counting matrix from Definition 2.3 is a signature matrix for different values of $k$ and gathered the results in Table 5.

<table><caption>**Tab. 5:** Signs of the determinants of reduced expressions of $w_\circ$ in $c^k w_\circ(c)$ for the counting matrix associated to multi-associahedra of type $A_4$.</caption><thead><tr><th>k</th><th>good signs</th><th>bad signs</th><th>zero</th><th>total</th></tr></thead><tbody><tr><td>1</td><td>42</td><td>0</td><td>0</td><td>42</td></tr><tr><td>2</td><td>593</td><td>0</td><td>1</td><td>594</td></tr><tr><td>3</td><td>4702</td><td>0</td><td>17</td><td>4719</td></tr><tr><td>4</td><td>25905</td><td>6</td><td>115</td><td>26026</td></tr></tbody></table>

In the cases $k = 2$ and $k = 3$ ($\Delta_{9,2}$ and $\Delta_{11,3}$) almost all determinants had the right signs with the exception of a few that were equal to zero. We found complete simplicial fan realizations in these cases by modifying some of the columns involved in the zero determinants, in such a way that they become non-zero determinants with the right signs. These modifications were small enough to make sure that all other determinants still have good signs. Note that we are not able to obtain complete simplicial fan realizations for the case $k = 4$ because such a small modification would not correct the bad signs that appear.

**Example 6.1 (Multi-associahedra $\Delta_{9,2}$ and $\Delta_{11,3}$)** The multi-associahedron $\Delta_{9,2}$ can be realized as the complete simplicial fan whose rays are the row vectors of the matrix on the left below and whose cones are spanned by the row vectors corresponding to faces of $\Delta_{9,2}$. The pairs of numbers on the left of the matrix are the 2-relevant diagonals of the 9-gon associated to each of the rows of the matrix. The multi-associahedron $\Delta_{11,3}$ can be realized as the complete simplicial fan whose rays are the row vectors of the matrix on the right below and whose cones are spanned by the row vectors corresponding to faces of $\Delta_{11,3}$. The pairs of numbers on the left of the matrix are the 3-relevant diagonals of the 11-gon associated to each of the rows of the matrix. Remarkably, these 2 fans are not the normal fan of polytopes.
[DLRS10] Jesús A. De Loera, Jörg Rambau, and Francisco Santos. *Triangulations*, volume 25 of *Algorithms and Computation in Mathematics*. Springer-Verlag, Berlin, 2010.

[Hum92] James E. Humphreys. *Reflection groups and Coxeter groups*. Cambridge Studies in Advanced Mathematics. 29 (Cambridge University Press), 1992.

[Jon05] Jakob Jonsson. Generalized triangulations and diagonal-free subsets of stack polyominoes. *J. Comb. Theory, Ser. A*, 112(1):117-142, 2005.

[KM04] Allen Knutson and Ezra Miller. Subword complexes in Coxeter groups. *Adv. Math.*, 184(1):161-176, 2004.

[KM05] Allen Knutson and Ezra Miller. Gröbner geometry of Schubert polynomials. *Ann. Math.*, 161(3):1245-1318, 2005.

[MHPS12] Folkert Müller-Hoissen, Jean Marcel Pallo, and Jim Stasheff, editors. *Associahedra, Tamari lattices and related structures*, volume 299 of *Progress in Mathematics*. Birkhäuser Boston Inc., Boston, MA, 2012.

[PP12] Vincent Pilaud and Michel Pocchiola. Multitriangulations, pseudotriangulations and primitive sorting networks. *Discrete Comput. Geom.*, 48(1):142-191, 2012.

[PS09] Vincent Pilaud and Francisco Santos. Multitriangulations as complexes of star polygons. *Discrete Comput. Geom.*, 41(2):284-317, 2009.

[PS12] Vincent Pilaud and Francisco Santos. The brick polytope of a sorting network. *European J. Combin.*, 33(4):632-662, 2012.

[PS15] Vincent Pilaud and Christian Stump. Brick polytopes of spherical subword complexes: A new approach to generalized associahedra. *Adv. Math.*, 276:1-61, 2015.

[RR13] Victor Reiner and Yuval Roichman. Diameter of graphs of reduced words and galleries. *Transactions of the American Mathematical Society*, 365(5):2779-2802, 2013.

[RSS03] Günter Rote, Francisco Santos, and Ileana Streinu. Expansive motions and the polytope of pointed pseudo-triangulations. In *Discrete and computational geometry*, volume 25 of *Algorithms Combin.*, pages 699-736. Springer, Berlin, 2003.

[S+14] William A. Stein et al. *Sage Mathematics Software (Version 6.2)*. The Sage Development Team, 2014.

[SS12] Luis Serrano and Christian Stump. Maximal fillings of moon polyominoes, simplicial complexes, and Schubert polynomials. *Electron. J. Combin.*, 19(1):P16, January 2012.

[Stu11] Christian Stump. A new perspective on *k*-triangulations. *J. Combin. Theory Ser. A*, 118(6):1794-1800, 2011.

[Tit69] Jacques Tits. Le problème des mots dans les groupes de Coxeter. In *Symposia Mathematica (INDAM, Rome, 1967/68), Vol. 1*, pages 175-185. Academic Press, London, 1969.