# Diameters and geodesic properties of generalizations of the associahedron

Cesar Ceballos, Thibault Manneville, Vincent Pilaud, Lionel Pournin

► To cite this version:

Cesar Ceballos, Thibault Manneville, Vincent Pilaud, Lionel Pournin. Diameters and geodesic properties of generalizations of the associahedron. 27th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2015), Jul 2015, Daejeon, South Korea. pp.345-356, 10.46298/dmtcs.2540. hal-01337812

HAL Id: hal-01337812

https://hal.science/hal-01337812

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
# Diameters and geodesic properties of generalizations of the associahedron

C. Ceballos<fnref n="1" />*, T. Manneville<fnref n="2" />, V. Pilaud<fnref n="3" />, and L. Pournin<fnref n="4" />

**Abstract.** The *n*-dimensional associahedron is a polytope whose vertices correspond to triangulations of a convex (*n* + 3)-gon and whose edges are flips between them. It was recently shown that the diameter of this polytope is 2*n* − 4 as soon as *n* > 9. We study the diameters of the graphs of relevant generalizations of the associahedron: on the one hand the generalized associahedra arising from cluster algebras, and on the other hand the graph associahedra and nestohedra. Related to the diameter, we investigate the non-leaving-face property for these polytopes, which asserts that every geodesic connecting two vertices in the graph of the polytope stays in the minimal face containing both.

**Résumé.** L'associaèdre de dimension *n* est un polytope dont les sommets correspondent aux triangulations d'un (*n* + 3)-gone convexe et dont les arêtes sont les échanges entre ces triangulations. Il a été récemment démontré que le diamètre de ce polytope est 2*n* − 4 dès que *n* > 9. Nous étudions les diamètres des graphes de certaines généralisations de l'associaèdre : d'une part les associaèdres généralisés provenant des algèbres amassées, et d'autre part les associaèdres de graphes et les nestoèdres. En lien avec le diamètre, nous étudions si toutes les géodésiques entre deux sommets de ces polytopes restent dans la plus petite face les contenant.

**Keywords:** flip graph diameter, non-leaving-face property, generalized associahedra, graph associahedra

The *n*-dimensional *associahedron* is a convex polytope whose vertices are in correspondence with triangulations of a convex (*n* + 3)-gon and whose edges are flips between them. See Figure 1 (left). Motivated by efficiency of repeated access and information update in binary search trees, D. Sleator, R. Tarjan and W. Thurston [STT88] gave an asymptotic estimate of the diameter of the associahedron, which was recently proved to be exact for all *n* > 9 by L. Pournin [Pou14b]:

**Theorem 1 ([STT88, Pou14b])** *The diameter of the *n*-dimensional associahedron is 2*n* − 4 for *n* > 9.*

<footnote n="1">¹Department of Mathematics and Statistics, York University, Toronto</footnote>

<footnote n="2">²Laboratoire d'Informatique de l'École Polytechnique, Palaiseau, France</footnote>

<footnote n="3">³CNRS & Laboratoire d'Informatique de l'École Polytechnique, Palaiseau, France</footnote>

<footnote n="4">⁴Laboratoire d'Informatique de Paris-Nord, Université Paris 13, Villetaneuse, France</footnote>

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

<footnote>‡thibault.maneville@lix.polytechnique.fr</footnote>

<footnote>§vincent.pilaud@lix.polytechnique.fr. Supported by the Spanish MICINN grant MTM2011-22792 and the French ANR grant EGOS (12 JS02 002 01).</footnote>

<footnote>¶lionel.pournin@univ-paris13.fr. Supported by Ville de Paris through *Émergences* project *Combinatoire à Paris*.</footnote>
<figure><img src="image_2.png" /><figcaption>**Fig. 1:** The generalized associahedra of type $A_3$ (left), type $B_3/C_3$ (middle), and type $D_3$ (right).</figcaption></figure>

Note that the upper bound is rather simple: a triangulation of the $(n + 3)$-gon with $d_i$ internal diagonals incident to vertex $i$ can be transformed by $n - d_i$ flips to the fan triangulation where all internal diagonals are incident to vertex $i$. Two triangulations $T$ and $T'$ can therefore be connected by at most $2n - \max_{i \in [n+3]}(d_i + d'_i) \le 2n - 4 + 6/(n - 3)$ flips, hence the diameter is at most $2n - 4$ when $n > 9$. Proving the lower bound is far more complicated: a candidate for a diametral pair of triangulations is exhibited for all $n$ in [Pou14b], and an induction formula on their flip distance is obtained by boundary edge contractions. The proof uses the following property of geodesics in the associahedron.

**Proposition 2 ([STT88])** *The associahedron has the non-leaving-face property: every geodesic connecting two vertices in the graph of the associahedron stays in the minimal face containing both. In other words, the common edges of two triangulations are never flipped along a geodesic between them.*

This paper reports on recent extensions of Theorem 1 and Proposition 2 developed in [Pou14a, CP14, MP14] for relevant generalizations of the classical associahedron. We first discuss the diameters of generalized associahedra, which where introduced by S. Fomin and A. Zelevinsky to encode the combinatorics of the finite type cluster complexes [FZ03a, FZ03b] and realized later as convex polytopes by different methods [CFZ02, HLT11, PS15, Ste13]. There is one generalized associahedron for each finite Coxeter group, among which the three infinite families of type A (classical associahedra), of types B or C (cyclohedra), and of type D. For these families, the graphs of the associahedra can be interpreted as the flip graphs on certain geometric models: triangulations in type A, centrally symmetric triangulations in type B/C, and centrally symmetric pseudotriangulations in type D. See Figure 1. We use these geometric models in Section 1 to obtain estimates for the diameters of type B/C associahedra [Pou14a] and a precise formula for the diameters of type D associahedra [CP14].

**Theorem 3 ([Pou14a, CP14])** (i) *The diameter of the $n$-dimensional associahedron of type $B/C$ is asymptotically $5n/2$. More precisely, it is at least $5n/2 - 4\sqrt{n} - 4$ and at most $\lceil 5n/2 \rceil - 2$.*

(ii) *The diameter of the $n$-dimensional associahedron of type $D$ is $2n - 2$ for all $n$.*

Note that the type $I_2(p)$ associahedron is a $(p+2)$-gon with diameter $\lfloor p/2 \rfloor + 1$. For completeness, we gather below the diameters of the small rank generalized associahedra (except types $D$ and $I$ which are completely settled by the previous formulas). They were reported in [STT88] for type $A$, in [Pou14a] for type $B$, and were computed using Stump's Sage package on subword complexes for exceptional types.

<table><thead><tr><th rowspan="2">type<br>rank<br>diam.</th><th colspan="8">A</th><th colspan="8">B/C</th><th>H</th><th>F</th><th>E</th></tr><tr><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th><th>9</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th><th>9</th><th>10</th><th>11</th><th>12</th><th>3</th><th>4</th><th>4</th><th>6</th><th>7</th><th>8</th></tr></thead><tbody><tr><td></td><td>2</td><td>4</td><td>5</td><td>7</td><td>9</td><td>11</td><td>12</td><td>15</td><td>3</td><td>5</td><td>7</td><td>9</td><td>11</td><td>14</td><td>16</td><td>18</td><td>21</td><td>23</td><td>25</td><td>6</td><td>10</td><td>8</td><td>11</td><td>14</td><td>19</td></tr></tbody></table>
<figure><img src="image_3.png" /><figcaption>**Fig. 2:** The path associahedron (classical associahedron), the cycle associahedron (cyclohedron), the tripod associahedron (stellohedron), and the complete graph associahedron (permutahedron).</figcaption></figure>

Section 2 is devoted to the extension of Proposition 2 to types $B/C$ and $D$ obtained in [CP14].

**Proposition 4 ([CP14]** All type A, B/C, or D associahedra fulfill the non-leaving-face property.

As for the diameter, we used the computer software Sage and a breadth first search algorithm to check this property for the exceptional types $H_3, H_4, F_4$ and $E_6$. This time-consuming verification was still to be done for types $E_7$ and $E_8$ when N. Williams gave a type-free proof for all finite Coxeter groups [Wil15].

Section 3 reports on the results of [MP14] on diameter bounds and the non-leaving-face property for graph associahedra. These polytopes were defined and constructed by M. Carr and S. Devadoss in [CD06]. See also [Pos09, FS05, Zel06] for generalizations and alternative constructions. Given a finite graph G, a G-associahedron is a simple convex polytope whose combinatorial structure encodes the connected subgraphs of G and their nested structure. Its vertices correspond to maximal tubings, i.e. collections of tubes (connected induced subgraphs) of G which are pairwise nested, or disjoint and non-adjacent, and its edges are flips between them. Specific families of graph-associahedra provide relevant families of polytopes: path associahedra are classical type A associahedra, cycle associahedra are cyclohedra (a.k.a. type B/C associahedra), and complete graph associahedra are type A permutahedra. See Figure 2 for 3-dimensional examples. We denote by $\mathcal{F}(G)$ the 1-skeleton of the G-associahedron and by $\delta(\mathcal{F}(G))$ its diameter. We obtained the following structural results.

**Theorem 5 ([MP14]** The diameter $\delta(\mathcal{F}(G))$ is non-decreasing: $\delta(\mathcal{F}(G)) \le \delta(\mathcal{F}(G'))$ for any $G \subseteq G'$.

Contrarily to the generalized associahedra, the non-leaving-face property is not satisfied for all faces of the G-associahedron (an example is given in Figure 9). However, we obtained the following statement.

**Proposition 6 ([MP14]** Any tubing on a geodesic between two tubings $T$ and $T'$ in the flip graph $\mathcal{F}(G)$ contains any common upper set to the inclusion posets of $T$ and $T'$.

In fact, Theorem 5 and Proposition 6 extend to all *nestohedra*, defined in [Pos09, FS05]. Finally, using Theorem 5 and Proposition 6, as well as the lower bound on the diameter of the associahedron [Pou14b] and the diameter of the permutahedron, we obtain the following inequalities on the diameter $\delta(\mathcal{F}(G))$.

**Theorem 7 ([MP14]** For any connected graph G on $n+1$ vertices, the diameter $\delta(\mathcal{F}(G))$ is bounded by

$$2n - 18 \le \delta(\mathcal{F}(G)) \le \binom{n+1}{2}.$$
# 1 Diameters of type $B/C$ and $D$ associahedra

In this section, we discuss the proof of Theorem 3. In both cases, the proof is based on the correspondence between the vertices of the generalized associahedra and certain geometric configurations.

## 1.1 Type $B/C$

The vertices of the $n$-dimensional type $B/C$ associahedron correspond to centrally symmetric triangulations of a centrally symmetric $(2n+2)$-gon, and the edges correspond to centrally symmetric flips between them (i.e. the flip of a long diagonal, or the simultaneous flips of two centrally symmetric internal diagonals). See Figure 1 (middle). We use this interpretation to prove Theorem 3 (i).

**Proof of Theorem 3 (i) (sketch):** For the upper bound, consider two centrally symmetric triangulations $T, T'$ of the $(2n+2)$-gon. Label the vertices of the $(2n+2)$-gon cyclically by $0, \dots, n, \bar{0}, \dots, \bar{n}$ such that the long diagonals of $T$ and $T'$ get labels $[0, \bar{0}]$ and $[x, \bar{x}]$ where $0 \le x \le n/2$. Then the sequence of flips illustrated in Figure 3 provides a path from $T$ to $T'$ of length at most $\lceil 5n/2 \rceil - 2$. Indeed, as already mentioned in the introduction, any triangulation of an $m$-gon can be transformed in at most $m-2$ flips to any fan triangulation (where all internal diagonals are incident to the same vertex).

<figure><img src="image_4.png" /><figcaption>**Fig. 3:** A path of at most $2n + x - 2$ flips between two arbitrary centrally symmetric triangulations.</figcaption></figure>

As in type $A$, the lower bound is more involved. In Figure 4, we sketch a pair of centrally symmetric triangulations of the $(2n+2)$-gon. Red edges are attached to vertices $0$ and $\bar{0}$ in the left triangulation, and the other edges form zigzags. Let $a$ denote half the number of red edges plus 1.

<figure><img src="image_5.png" /><figcaption>**Fig. 4:** A pair of centrally symmetric triangulations far apart in the graph of the cyclohedron, here with $a = 3$</figcaption></figure>

Using edge contractions as in [Pou14b] within a larger family of pairs of centrally symmetric triangulations stable by contractions, it is proved in [Pou14a] that the distance between these two triangulations is at least $5(n-a)/2 - (n+2)/a - 4$. Choosing the value of $a$ appropriately yields the lower bound $5n/2 - 4\sqrt{n} - 4$. We refer to [Pou14a] for the complete proof. □
## 1.2 Type D

S. Fomin and A. Zelevinsky also introduced a geometric model for type D based on centrally symmetric triangulations of the 2n-gon with colors and special rules for the long diagonals [FZ03b, FZ03a]. For our purposes, it is more convenient to slightly perturb this model as follows (see Figures 1 (right) and 5). We consider a regular convex 2n-gon together with a disk D placed at its center, whose radius is small enough such that D only intersects the long diagonals of the 2n-gon. Let $\mathbb{D}_n$ denote the resulting configuration. The *chords* of $\mathbb{D}_n$ are all the diagonals of the 2n-gon, but the long ones, plus all the segments tangent to the disk D and with one endpoint among the vertices of the 2n-gon. Each vertex p is adjacent to two of the latter chords; we denote by $p^L$ (resp. by $p^R$) the chord emanating from p and tangent on the left (resp. right) to the disk D, and call these chords *central*. The faces of the type $\mathbb{D}_n$ associahedron can be interpreted geometrically on the configuration $\mathbb{D}_n$ as follows:

(i) Facets correspond to *centrally symmetric pairs of chords* of the geometric configuration $\mathbb{D}_n$.

(ii) Faces correspond to crossing-free centrally symmetric sets of chords. The face lattice corresponds to the reverse inclusion lattice on crossing-free centrally symmetric sets of chords.

(iii) Vertices correspond to *centrally symmetric pseudotriangulations* of $\mathbb{D}_n$ (i.e. inclusion maximal centrally symmetric crossing-free sets of chords of $\mathbb{D}_n$). Each pseudotriangulation of $\mathbb{D}_n$ contains exactly 2n chords, and partitions $\text{conv}(\mathbb{D}_n) \setminus D$ into *pseudotriangles* (i.e. interiors of simple closed curves with three convex corners related by three concave chains).

(iv) Edges correspond to *flips* of centrally symmetric pairs of chords between centrally symmetric pseudotriangulations of $\mathbb{D}_n$. A flip in a pseudotriangulation $T$ replaces an internal chord $e$ by the unique other internal chord $f$ such that $(T \setminus e) \cup f$ is again a pseudotriangulation of $T$. To be more precise, deleting $e$ in $T$ merges the two pseudotriangles of $T$ incident to $e$ into a pseudoquadrangle $\square$ (i.e. the interior of a simple closed curve with four convex corners related by four concave chains), and adding $f$ splits the pseudoquadrangle $\square$ into two new pseudotriangles.

See [RSS08] for a complete survey on pseudotriangulations. We can now prove Theorem 3 (ii).

**Proof of Theorem 3 (ii):** Define the *left star* $S^L$ as the pseudotriangulation containing all left central chords $p^L$ for $p \in [n] \cup [\bar{n}]$. Similarly, the *right star* $S^R$ contains all right central chords $p^R$ for $p \in [n] \cup [\bar{n}]$. We claim that $S^L$ and $S^R$ are at distance $2n-2$ and realize the diameter of the type D associahedron.

First, Figure 5 illustrates a path in the flip graph that uses exactly $2n-2$ flips between $S^L$ and $S^R$. Moreover, if a centrally symmetric pseudotriangulation has more than two pairs of left central chords, then none of the possible flips produces a pair of right central chords. This means that we need to apply at least $n-2$ flips to the left star until we are able to make a flip that produces a pair of right central chords. Since the right star has $n$ pairs of right central chords, we need at least $n$ additional flips to produce it. This proves that any path between $S^L$ and $S^R$ uses at least $(n-2)+n = 2n-2$ flips. This proves that $S^L$ and $S^R$ are at distance $2n-2$.

The same arguments ensure that:

(i) If $T$ contains $\ell \ge 1$ centrally symmetric pairs of left central chords $\{p^L, \bar{p}^L\}$, then $T$ is precisely at distance $n-\ell$ from the left star $S^L$ and precisely at distance $n+\ell-2$ from the right star $S^R$.

(ii) If $T$ contains $r \ge 1$ centrally symmetric pairs of right central chords $\{p^R, \bar{p}^R\}$, then $T$ is precisely at distance $n-r$ from the right star $S^R$ and precisely at distance $n+r-2$ from the left star $S^L$.

Consider now two pseudotriangulations $T$ and $T'$ of $\mathbb{D}_n$. Let $\ell$ and $\ell'$ (resp. $r$ and $r'$) be the number of left (resp. right) central pairs of chords in $T$ and $T'$ respectively. If $T$ and $T'$ contain a central pair of chords of the same kind, say left, then they can be connected by a path passing through the left star $S^L$.
<figure><img src="image_6.png" /><figcaption>Fig. 5: The distance between the two stars $S^L$ and $S^R$ is $2n-2$.</figcaption></figure>

of length $n - \ell + n - \ell' \le 2n - 2$. If not, we can assume without loss of generality that $\ell \ge 1$ and $r' \ge 1$. Then there are two paths connecting $T$ and $T'$ passing through the star triangulations $S^L$ and $S^R$ respectively of length $(n-\ell)+(n+r'-2) = 2n-2-\ell+r'$ and $(n+\ell-2)+(n-r') = 2n-2+\ell-r'$. Clearly, one of these two numbers is less than or equal to $2n-2$. $\square$

## 2 Non-leaving-face property and relatives

In this section, we focus on geodesic properties. We consider three properties for a face $F$ of a polytope $P$:

**NLFP:** $F$ has the *non-leaving-face property* in $P$ if $F$ contains all geodesics connecting two vertices of $F$ in the graph of $P$.

**SNLFP:** $F$ has the *strong non-leaving-face property* in $P$ if any path connecting two vertices $v, w$ of $F$ in the graph of $P$ and leaving the face $F$ has at least two more steps than a geodesic between $v$ and $w$.

**EFP:** $F$ has the *entering-face property* in $P$ if for any vertices $u, v, w$ of $P$ such that $u \notin F$, $v, w \in F$, and $u$ and $v$ are neighbors in the graph of $P$, there exists a geodesic connecting $u$ and $w$ whose first edge is the edge from $u$ to $v$.

For a face $F$ of a polytope $P$, we have EFP $\iff$ SNLFP $\iff$ NLFP. However, the reverse of the last implication is wrong (for example for the simplex). Among classical polytopes the $n$-dimensional cube, permutahedron, associahedron, and cyclohedron all satisfy the EFP (see Proposition 9 below).

The non-leaving-face property obviously implies the more classical non-revisiting-face property introduced in the context of the Hirsch conjecture. In fact, all the generalizations of the associahedron treated in this paper are flag simplicial complexes and thus satisfy the Hirsch bound [AB14].

### 2.1 Normalization

A normalization is a useful tool to transform a geodesic between two triangulations into a geodesic starting with a prescribed flip. In particular, it is a projection from the graph of the associahedron to the graph of one of its facets. We use the terms “triangulation” and “diagonal” generically for the corresponding geometric models in types A, $B/C$, and $D$.

**Proposition 8 ([STT88, CP14]** For any type A, $B/C$, or $D$, and for any diagonal $\chi$, there exists a normalization $N_\chi$, that is, a map $T \mapsto N_\chi(T)$ satisfying the following properties:

(P0) for any triangulation $T$, the normalization $N_\chi(T)$ is a triangulation containing $\chi$;

(P1) if $\chi \in T$, then $N_\chi(T) = T$;

(P2) if $T, T'$ are two adjacent triangulations, then $N_\chi(T)$ and $N_\chi(T')$ coincide or are adjacent;

(P3) if $T, T'$ are two adjacent triangulations with $\chi \in T' \setminus T$, then $N_\chi(T) = N_\chi(T') = T'$.
<figure><img src="image_7.png" /><figcaption>Fig. 6: Normalizations in types A, B/C, and D.</figcaption></figure>

**Proof (sketch):** This proposition is proved case by case using the geometric models in types A, B/C, and D. These maps are illustrated in Figure 6 and can be informally described as follows:

* In type A, $N_\chi(T)$ is obtained from $T$ by pulling all diagonals crossing $\chi$ towards one endpoint of $\chi$.

* In type B/C, $N_\chi(T)$ is obtained from $T$ by pulling all diagonals crossing $\chi$ and $\bar{\chi}$

– towards opposite endpoint of $\chi$ and $\bar{\chi}$ if $\chi \neq \bar{\chi}$,

– from the center towards both endpoints of $\chi$ if $\chi = \bar{\chi}$.

* In type D, $N_\chi(T)$ is obtained from $T$ by

– pulling all diagonals crossing $\chi$ and $\bar{\chi}$ towards opposite endpoint of $\chi$ and $\bar{\chi}$ if $\chi$ is not central,

– replacing the pseudotriangles crossing $\chi$ and $\bar{\chi}$ by the star containing $\chi$ if $\chi$ is central.

One can check that these maps produce non-crossing configurations. Moreover, they send triangulations to triangulations, and almost triangulations (i.e. triangulations minus one internal diagonal) to either triangulations or almost triangulations. The properties of Proposition 8 are consequences of these observations.
The reader is invited to consult [CP14] for more details. $\square$

## 2.2 Entering-face-property for generalized associahedra

Using the normalization from the previous section, we can prove the non-leaving-face property for types A, B/C, or D associahedra. We prove in fact the following stronger statement.

**Proposition 9 ([STT88, CP14])** All type A, B/C, or D associahedra have the entering face property: if $T$ and $T'$ are two triangulations and $\chi$ is a diagonal in $T \setminus T'$ such that the flip of $\chi$ in $T$ produces a diagonal that belongs to $T'$, then there exists a geodesic between $T$ and $T'$ which starts by the flip of $\chi$.

**Proof:** Let $T = T_0, T_1, \dots, T_k = T'$ be an arbitrary geodesic between $T$ and $T'$. Consider the sequence $T = T_0, N_{\chi'}(T_0), N_{\chi'}(T_1), \dots, N_{\chi'}(T_k)$. By Property (P1) above, the last triangulation in this sequence is $T'$. By Property (P3), the first two triangulations are connected by a flip. Since there exists at least one $i$ such that $\chi' \in T_{i+1} \setminus T_i$, Property (P3) also ensures that $N_{\chi'}(T_i) = N_{\chi'}(T_{i+1})$. Finally, Property (P2) asserts that any two consecutive triangulations in the remaining sequence either coincide or are adjacent. Erasing duplicated consecutive triangulations in this sequence gives a normalized path from $T$ to $T'$, which starts by the flip of $\chi$, and is a geodesic since it is not longer than the geodesic $T = T_0, T_1, \dots, T_k = T'$. $\square$
# 3 Graph associahedra

## 3.1 Graph associahedra and nestohedra

Let V be an (n + 1)-elements ground set, and let G be a simple graph on V with $\pi_0(G)$ connected components. We denote by $G[U]$ the subgraph of G induced by a subset U of V.

A *tube* of G is a non-empty subset $t$ of V that induces a connected subgraph of G. A *tube* is *proper* if it does not induce a connected component of G. The set of all tubes of G is called the *graphical building set* of G and denoted by $B(G)$. We moreover denote by $B(G)_{max}$ the set of inclusion maximal tubes of $B(G)$, i.e. the vertex sets of connected components of G.

Two tubes $t$ and $t'$ are *compatible* if they are nested (i.e. $t \subseteq t'$ or $t' \subseteq t$), or disjoint and non-adjacent (i.e. $t \cup t'$ is not a tube of G). A *tubing* on G is a set of pairwise compatible tubes of G. A tubing is *proper* if it contains only proper tubes and *loaded* if it contains $B(G)_{max}$. Since inclusion maximal tubes are compatible with all tubes, we can transform any tubing $T$ into a proper tubing $T \setminus B(G)_{max}$ or into a loaded tubing $T \cup B(G)_{max}$. Figure 7 illustrates these notions on a graph with 9 vertices.

The *nested complex* on G is the simplicial complex $N(G)$ of all proper tubings on G. This complex is known to be the boundary complex of the *graph associahedron* Asso$(G)$, which is an $(n + 1 - \pi_0(G))$-dimensional simple polytope. Here, we focus on the *flip graph* $\mathcal{F}(G)$ whose vertices are maximal proper tubings on G and whose edges connect adjacent maximal proper tubings, i.e. which only differ by two tubes. To simplify the presentation, it is sometimes more convenient to consider the *loaded flip graph*, obtained from $\mathcal{F}(G)$ by loading all its vertices with $B(G)_{max}$, and still denoted by $\mathcal{F}(G)$. See Figure 2. We denote by $\delta(\mathcal{F}(G))$ the diameter of the flip graph $\mathcal{F}(G)$.

Flips in graph associahedra can be explicitly described as follows. For a tube $t$ in a tubing $T$, define $\lambda(t, T) := t \setminus \bigcup \{t' \in T \mid t' \not\subseteq t\}$. Note that the tubing is maximal if and only if $\lambda(t, T)$ is a singleton for all $t \in T$. Consider a tube $t$ in a maximal proper tubing $T$, with $\lambda(t, T) = \{v\}$. Let $\bar{t}$ denote the smallest element of $T \cup B(G)_{max}$ strictly containing $t$, and denote its label by $\lambda(\bar{t}, T) = \{v'\}$. Then the unique tube $t'$ such that $T' := T \Delta \{t, t'\}$ is again a proper tubing on G is the connected component of the induced subgraph $G[\bar{t} \setminus \{v\}]$ containing $v'$. See Figure 7 (right) for an illustration.

<figure><img src="image_8.png" /><figcaption>**Fig. 7:** (Left) A tubing, a maximal proper tubing, and a maximal loaded tubing. (Right) A flip between two maximal tubings.</figcaption></figure>
Graph associahedra are graphical examples of nestohedra. We recall the definitions of building set and nested complex needed here and refer to [Pos09, FS05, Zel06] for more details and motivation. A *building set* on a ground set V is a collection B of non-empty subsets of V such that

(B1) if $b, b' \in B$ and $b \cap b' \neq \emptyset$, then $b \cup b' \in B$, and

(B2) B contains all singletons $\{v\}$ for $v \in V$.

We denote by $B_{\max}$ the set of inclusion maximal elements of B and call *proper* the elements of $B \setminus B_{\max}$.
A *B-nested set* on B is a subset N of B such that

(N1) for any $n, n' \in N$, either $n \subseteq n'$ or $n' \subseteq n$ or $n \cap n' = \emptyset$, and

(N2) for any $k \ge 2$ pairwise disjoint sets $n_1, \dots, n_k \in N$, the union $n_1 \cup \dots \cup n_k$ is not in B.

A B-nested set N is proper if $N \cap B_{\max} = \emptyset$ and loaded if $B_{\max} \subseteq N$. The B-nested complex is the $(|V| - |B_{\max}|)$-dimensional simplicial complex $N(B)$ of all proper nested sets on B. It can be realized geometrically as the boundary complex of the polar of the *nestohedron* Nest(B), constructed e.g. in [Pos09, FS05, Zel06]. We denote by $\delta(F(B))$ the diameter of the graph $F(B)$ of Nest(B). It is again more convenient to regard the vertices of $F(B)$ as maximal loaded nested sets.

## 3.2 Non-decreasing diameters

**Theorem 10 ([MP14])** $\delta(\mathcal{F}(\bar{B})) \le \delta(\mathcal{F}(B))$ for any two building sets B, $\bar{B}$ on V such that $\bar{B} \subseteq B$.

**Proof (sketch):** We first define a map $\Omega$ which transforms elements of B to subsets of $\bar{B}$ as follows: for $b \in B$ (proper or not), define $\Omega(b)$ as the coarsest partition of b into elements of $\bar{B}$. For a nested set N on B, we then define $\Omega(N) := \bigcup_{n \in N} \Omega(n)$.

We prove in [MP14, Coro. 13] that the map $\Omega$ induces a graph surjection from the loaded flip graph $\mathcal{F}(B)$ onto the loaded flip graph $\mathcal{F}(\bar{B})$, i.e. a surjective map from maximal nested sets on B to maximal nested sets on $\bar{B}$ such that adjacent nested sets on B are sent to identical or adjacent nested sets on $\bar{B}$. For any $\bar{B}$-nested sets $\bar{N}$ and $\bar{N}'$, the image of a geodesic path in $\mathcal{F}(\bar{B})$ from $\Omega^{-1}(\bar{N})$ to $\Omega^{-1}(\bar{N}')$ yields a path in $\mathcal{F}(\bar{B})$ from $\bar{N}$ to $\bar{N}'$ no longer than $\delta(\mathcal{F}(\bar{B}))$. Hence $\delta(\mathcal{F}(\bar{B})) \le \delta(\mathcal{F}(B))$.

This surjection map $\Omega$ can also be interpreted geometrically. It follows from the construction of [CD06, Pos09] that the nestohedron Nest($\bar{B}$) can be obtained from the nestohedron Nest($\bar{B}$) by successive face truncations. Geometrically, this operation replaces the truncated face $F$ by its Cartesian product with a simplex of codimension $\dim(F) + 1$. Therefore, a path in the graph of Nest($\bar{B}$) naturally projects to a shorter path in the graph of Nest($\bar{B}$). $\square$

## 3.3 Diameter bounds for graph associahedra

Using Theorem 5 and Proposition 6 (see Section 3.4), as well as the lower bound on the diameter of the associahedron [Pou14b] and the diameter of the permutahedron, we obtain the inequalities of Theorem 7.

**Proof of Theorem 7:** For the upper bound, we use that the diameter is non-decreasing (Theorem 5) and that the $n$-dimensional permutahedron has diameter $\binom{n+1}{2}$, the maximal number of inversions in a permutation of $S_{n+1}$. For the lower bound, we use again Theorem 5 to restrict the argument to trees. Let $T$ be a tree on $n+1$ vertices. We first discard some basic cases:

(i) If $T$ has precisely two leaves, then $T$ is a path and the graph associahedron Asso($T$) is the classical $n$-dimensional associahedron, whose diameter is known to be larger than $2n-4$ by [Pou14b].
<figure><img src="image_9.png" /><figcaption>Fig. 8: Decompositions of trees with 3 or 4 leaves.</figcaption></figure>

(ii) If $T$ has precisely 3 leaves, then it consists in 3 paths attached by a 3-valent node $v$, see Figure 8 (left). Let $w$ be a neighbor of $v$ and $P_1, P_2$ denote the connected components of $T \setminus w$. Observe that $P_1$ and $P_2$ are both paths and denote by $p_1 + 1$ and $p_2 + 1$ their respective lengths. Let $T'_1, T''_1$ (resp. $T'_2, T''_2$) be a diametral pair of maximal tubings on $P_1$ (resp. on $P_2$), and consider the maximal tubings $T' = T'_1 \cup T'_2 \cup \{P_1, P_2\}$ and $T'' = T''_1 \cup T''_2 \cup \{P_1, P_2\}$ on the tree $T$. Finally, denote by $T$ the maximal tubing on $T$ obtained by flipping $P_1$ in $T'$. Since $\{P_1, P_2\}$ is a common upper set to the inclusion posets of $T'$ and $T''$, the EFP ensures that there exists a geodesic from $T$ to $T''$ that starts by the flip from $T$ to $T'$. Moreover, the NLFP ensures that the distance between $T'$ and $T''$ is realized by a path staying in the face of Asso($T$) corresponding to $\{P_1, P_2\}$, which is the product of a classical $p_1$-dimensional associahedron by a classical $p_2$-dimensional associahedron. Thus

$$ \delta(\mathcal{F}(T)) \geq 1 + \delta(\mathcal{F}(P_1)) + \delta(\mathcal{F}(P_2)) \geq 1 + (2p_1 - 4) + (2p_2 - 4) = 2(p_1 + p_2 + 2) - 11 = 2n - 11. $$

(iii) If $T$ has precisely 4 leaves, it either contains a single 4-valent node $v$ or precisely two 3-valent nodes $u, v$, see Figure 8 (middle and right). Define $w$ to be a neighbor of $v$, not located in the path between $u$ and $v$ in the latter situation. Then $w$ disconnects $T$ into a path $P$ on $p+1$ nodes and a tree $Y$ with $y+1$ nodes and precisely 3 leaves. A similar argument as in (ii) shows that

$$ \delta(\mathcal{F}(T)) \geq 1 + \delta(\mathcal{F}(P)) + \delta(\mathcal{F}(Y)) \geq 1 + (2p - 4) + (2y - 11) = 2(p + y + 2) - 18 = 2n - 18. $$

Assume now that the tree $T$ has $k \ge 5$ leaves $l_1, \dots, l_k$. Let $\bar{V} := V \setminus \{l_1, \dots, l_k\}$ and $\bar{T} = T[\bar{V}]$ denote the tree obtained by deletion of the leaves of $T$. By induction hypothesis, there exists two tubings $\bar{T}$ and $\bar{T}'$ on $\bar{T}$ at distance at least $2(n-k) - 18$. Let $t_i := V \setminus \{l_1, \dots, l_i\}$ for $i \in [k]$, and $t'_j := V \setminus \{l_j, \dots, l_k\}$ for $j \in [k]$. We claim that the tubings $T := \bar{T} \cup \{t_1, \dots, t_k\}$ and $T' := \bar{T}' \cup \{t'_1, \dots, t'_k\}$ on $T$ are at distance at least $2n - 18$ from each other. To see it, consider the surjection $\Omega$ from the tubings on $T$ onto that of $\bar{T} \cup \{l_1, \dots, l_k\}$ as defined in Section 3.2. It sends a path $T = T_0, \dots, T_\ell = T'$ in $\mathcal{F}(T)$ to a path

$$ \bar{T} \cup \{\{l_1\}, \dots, \{l_k\}\} = \Omega(T_0), \dots, \Omega(T_\ell) = \bar{T}' \cup \{\{l_1\}, \dots, \{l_k\}\} $$

in $\mathcal{F}(\bar{T} \cup \{l_1, \dots, l_k\})$ with repeated entries. Since $\bar{T}$ and $\bar{T}'$ are at distance at least $2(n-k) - 18$ in the flip graph $\mathcal{F}(\bar{T})$, this path has at least $2(n-k) - 18$ non-trivial steps, so we must show that it has at least $2k$ repetitions. These repetitions appear whenever we flip a tube $t_i$ or $t'_j$. If we never flip the tube $t_k = \bar{V} = t'_1$ along the path $T = T_0, \dots, T_\ell = T'$, then we need at least $\binom{k}{2} \ge 2k$ flips to transform $\{t_1, \dots, t_k\}$ into $\{t'_1, \dots, t'_k\}$. Otherwise, we need to flip all $\{t_1, \dots, t_k\}$ and then back all $\{t'_1, \dots, t'_k\}$, which produces at least $2k$ repetitions. See [MP14, Thm. 18] for details. $\square$
**Remark 11** Simple arguments involving the graphical zonotope of G show that $\delta(\mathcal{F}(G))$ is in fact greater than the number of edges of G. In view of Theorem 5, it is tempting to ask for more correlations between the diameter $\delta(\mathcal{F}(G))$ and the number of edges of G. As far as trees are concerned, we understand better stars and their subdivisions. The diameter $\delta(\mathcal{F}(K_{1,n}))$ for the star $K_{1,n}$ is exactly $2n$ (for $n \ge 5$), see Figure 9. In fact, the diameter of the graph associahedron of any starlike tree (subdivision of a star) on $n+1$ vertices can be shown to be of order $2n$ and the diameter of any tree associahedron $\delta(\mathcal{F}(T))$ of order at most $n \log n$. The following question remains open.

**Question 12** Is there a family of trees $T_n$ on $n$ nodes such that $\delta(\mathcal{F}(T_n))$ is of order $n \log n$? More specifically, if $T_1 = K_{1,3}$ and $T_{k+1}$ is obtained by grafting two leaves to each leaf of $T_k$, what is $\delta(\mathcal{F}(T_k))$?

## 3.4 Non-leaving-face property

Contrarily to the classical associahedron, not all faces of a graph associahedron have the NLFP. A counterexample is given by the star with $n \ge 5$ branches: Figure 9 shows a path of length $2n$ between two maximal tubings $T$ and $T'$, while the minimal face containing $T$ and $T'$ is an $(n-1)$-dimensional permutahedron (see the face description in [CD06, Thm. 2.9]) and the graph distance from $T$ to $T'$ in this face is $(\frac{n}{2})$.

<figure><img src="image_10.png" /><figcaption>**Fig. 9:** A geodesic (of length $2n$) between two maximal tubings of the star that flips their common tube.</figcaption></figure>

We can however provide a sufficient condition for a face of a nestohedron to satisfy the NLFP. We call *upper ideal face* of the nestohedron $\text{Nest}(B)$ a face corresponding to a loaded nested set $N^\uparrow$ such that any element of $B \cup N^\uparrow$ compatible with $N^\uparrow$ is contained in a minimal element of $N^\uparrow$. The following statement specializes to the NLFP (and EFP) for the upper set faces of graph associahedra, see Proposition 6.

**Proposition 13 ([MP14])** Any *upper ideal face* of the *nestohedron Nest(B)* satisfies *SNLFP*.
References

[AB14] K. A. Adiprasito and B. Benedetti. The Hirsch conjecture holds for normal flag complexes. *Math. Oper. Res.*, 39(4):1340–1348, 2014.

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

[CFZ02] F. Chapoton, S. Fomin, and A. Zelevinsky. Polytopal realizations of generalized associahedra. *Canad. Math. Bull.*, 45(4):537–566, 2002.

[CP14] C. Ceballos and V. Pilaud. The diameter of type d associahedra and the non-leaving-face property. To appear in *European J. Combin*. (preprint, arXiv:1406.0368), 2014.

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

[FZ03a] S. Fomin and A. Zelevinsky. Cluster algebras. II. Finite type classification. *Invent. Math.*, 154(1):63–121, 2003.

[FZ03b] S. Fomin and A. Zelevinsky. Y-systems and generalized associahedra. *Ann. of Math. (2)*, 158(3):977–1018, 2003.

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

[MP14] T. Manneville and V. Pilaud. Graph properties of graph associahedra. Preprint, arXiv:1409.8114, 2014.

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

[Pou14a] L. Pournin. The asymptotic diameter of cyclohedra. Preprint, arXiv:1410.5259, 2014.

[Pou14b] L. Pournin. The diameter of associahedra. *Adv. in Math.*, 259:13–42, 2014.

[PS15] V. Pilaud and C. Stump. Brick polytopes of spherical subword complexes and generalized associahedra. *Adv. Math.*, 276:1–61, 2015.

[RSS08] G. Rote, F. Santos, and I. Streinu. Pseudo-triangulations — a survey. In *Surveys on discrete and comput. geom.*, volume 453 of *Contemp. Math.*, pages 343–410. Amer. Math. Soc., 2008.

[Ste13] S. Stella. Polyhedral models for generalized associahedra via Coxeter elements. *J. Algebraic Combin.*, 38(1):121–158, 2013.

[STT88] D. D. Sleator, R. E. Tarjan, and W. P. Thurston. Rotation distance, triangulations, and hyperbolic geometry. *J. Amer. Math. Soc.*, 1(3):647–681, 1988.

[Wil15] Nathan Williams. w-Associahedra are In-Your-Face. Preprint, arXiv:1502.01405, 2015.

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